Please use this identifier to cite or link to this item:
|Title:||Compact Encodings and Indexes for the Nearest Larger Neighbor Problem|
Satti, S. R.
|Presented at:||Algorithms and Computation - 9th International Workshop, WALCOM 2015. Dhaka, Bangladesh|
|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.|
|Rights:||Archived with reference to SHERPA/RoMEO and publisher website. The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-15612-5_6|
|Appears in Collections:||Conference Papers & Presentations, Dept. of Computer Science|
Files in This Item:
|paper_77(1).pdf||Post-review (final submitted)||385.3 kB||Adobe PDF||View/Open|
Items in LRA are protected by copyright, with all rights reserved, unless otherwise indicated.