University of Leicester
Browse
nlv_camera_ready.pdf (521.41 kB)

Encoding Nearest Larger Values

Download (521.41 kB)
conference contribution
posted 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.

History

Citation

Lecture Notes in Computer Science, 9133, pp. 385–395, 2015

Author affiliation

/Organisation/COLLEGE OF SCIENCE AND ENGINEERING/Department of Computer Science

Source

26th Annual Symposium on Combinatorial Pattern Matching, Ischia Island, Italy

Version

  • AM (Accepted Manuscript)

Published in

Lecture Notes in Computer Science

Publisher

Springer

issn

0302-9743

isbn

978-3-319-19928-3;978-3-319-19929-0

Copyright date

1007

Available date

2016-06-16

Publisher version

http://link.springer.com/chapter/10.1007/978-3-319-19929-0_33

Temporal coverage: start date

2015-06-29

Temporal coverage: end date

2015-07-01

Language

en

Usage metrics

    University of Leicester Publications

    Categories

    Keywords

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC