Please use this identifier to cite or link to this item: http://hdl.handle.net/2381/32178
Title: Encoding Nearest Larger Values
Authors: Nicholson, P. K.
Raman, Rajeev
First Published: 16-Jun-2015
Presented at: 26th Annual Symposium on Combinatorial Pattern Matching, Ischia Island, Italy
Start Date: 29-Jun-2015
End Date: 1-Jul-2015
Publisher: Springer
Citation: Lecture Notes in Computer Science, 9133, pp. 385–395, 2015
Abstract: In nearest larger value (NLV) problems, we are given an array A[1..n] of numbers, and need to preprocess A to answer queries of the following form: given any index i ∈ [1, n], return a “nearest” index j such that A[j] > A[i]. We consider the variant where the values in A are distinct, and we wish to return an index j such that A[j] > A[i] and |j − i| is minimized, the nondirectional NLV (NNLV) problem. We consider NNLV in the encoding model, where the array A is delete after preprocessing, and note that NNLV encoding problem has an unexpectedly rich structure: the effective entropy (optimal space usage) of the problem depends crucially on details in the definition of the problem. Using a new path-compressed representation of binary trees, that may have other applications, we encode NNLV in 1.9n + o(n) bits, and answer queries in O(1) time.
DOI Link: 10.1007/978-3-319-19929-0_33
ISSN: 0302-9743
ISBN: 978-3-319-19928-3
Links: http://hdl.handle.net/2381/32178
http://link.springer.com/chapter/10.1007%2F978-3-319-19929-0_33
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 http://dx.doi.org/10.1007/978-3-319-19929-0_33
Appears in Collections:Conference Papers & Presentations, Dept. of Computer Science

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


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