nlv_camera_ready.pdf (521.41 kB)
Encoding Nearest Larger Values
conference contributionposted on 2015-05-07, 10:24 authored by P. K. Nicholson, Rajeev Raman
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.
CitationLecture Notes in Computer Science, 9133, pp. 385–395, 2015
Author affiliation/Organisation/COLLEGE OF SCIENCE AND ENGINEERING/Department of Computer Science
Source26th Annual Symposium on Combinatorial Pattern Matching, Ischia Island, Italy
- AM (Accepted Manuscript)