Please use this identifier to cite or link to this item:
Title: Compact Encodings and Indexes for the Nearest Larger Neighbor Problem
Authors: Jo, S.
Raman, Rajeev
Satti, S. R.
First Published: 25-Feb-2015
Presented at: Algorithms and Computation - 9th International Workshop, WALCOM 2015. Dhaka, Bangladesh
Start Date: 26-Feb-2015
End Date: 28-Feb-2015
Publisher: Springer Verlag (Germany)
Citation: Lecture Notes in Computer Science, 2015, 8973, pp. 53-64
Abstract: Given a d-dimensional array, for any integer d > 0, the nearest larger value (NLV) query returns the position of the element which is closest, in L1 distance, to the query position, and is larger than the element at the query position. We consider the problem of preprocessing a given array, to construct a data structure that can answer NLV queries efficiently. In the 2-D case, given an n × n array A, we give an asymptotically optimal O(n 2 )-bit encoding that answers NLV queries in O(1) time. When A is a binary array, we describe a simpler O(n 2 )-bit encoding that also supports NLV queries in O(1) time. Using this, we obtain an index of size O(n 2 /c) bits that supports NLV queries in O(c) time, for any parameter c, where 1 ≤ c ≤ n, matching the lower bound. For the 1-D case we consider the nearest larger right value (NLRV) problem where the nearest larger value to the right is sought. For an array of length n, we obtain an index that takes O((n/c) log c) bits, and supports NLRV queries in O(c) time, for any any parameter c, where 1 ≤ c ≤ n, improving the earlier results of Fischer et al. and Jayapaul et al.
DOI Link: 10.1007/978-3-319-15612-5_6
ISSN: 0302-9743
ISBN: 978-3-319-15611-8
Version: Post-print
Status: Peer-reviewed
Type: Conference Paper
Rights: Archived with reference to SHERPA/RoMEO and publisher website. The final publication is available at Springer via
Appears in Collections:Conference Papers & Presentations, Dept. of Computer Science

Files in This Item:
File Description SizeFormat 
paper_77(1).pdfPost-review (final submitted)385.3 kBAdobe PDFView/Open

Items in LRA are protected by copyright, with all rights reserved, unless otherwise indicated.