University of Leicester
Browse
paper.pdf (363.27 kB)

Encoding range minima and range top-2 queries

Download (363.27 kB)
journal contribution
posted on 2014-05-28, 10:49 authored by Pooya Davoodi, Gonzalo Navarro, Rajeev Raman, S. Srinivasa Rao
We consider the problem of encoding range minimum queries (RMQs): given an array A[1..n] of distinct totally ordered values, to pre-process A and create a data structure that can answer the query RMQ(i,j), which returns the index containing the smallest element in A[i..j], without access to the array A at query time. We give a data structure whose space usage is 2n+o(n) bits, which is asymptotically optimal for worst-case data, and answers RMQs in O(1) worst-case time. This matches the previous result of Fischer and Heun, but is obtained in a more natural way. Furthermore, our result can encode the RMQs of a random array A in 1.919n+o(n) bits in expectation, which is not known to hold for Fischer and Heun’s result. We then generalize our result to the encoding range top-2 query (RT2Q) problem, which is like the encoding RMQ problem except that the query RT2Q(i,j) returns the indices of both the smallest and second smallest elements of A[i..j]. We introduce a data structure using 3.272n+o(n) bits that answers RT2Qs in constant time, and also give lower bounds on the effective entropy of the RT2Q problem.

History

Citation

Philosophical Transactions of the Royal Society A : Mathematical, Physical and Engineering Sciences, 2014, 372, 20130131

Author affiliation

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

Version

  • AM (Accepted Manuscript)

Published in

Philosophical Transactions of the Royal Society A : Mathematical

Publisher

The Royal Society

issn

1364-503X

eissn

1471-2962

Copyright date

2014

Available date

2015-04-22

Publisher version

http://rsta.royalsocietypublishing.org/content/372/2016/20130131.full.pdf+html

Language

en

Usage metrics

    University of Leicester Publications

    Categories

    Keywords

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC