University of Leicester
Browse
paper-88.pdf (519.53 kB)

Asympotically optimal encodings for range selection

Download (519.53 kB)
conference contribution
posted on 2014-10-22, 14:00 authored by Gonzalo Navarro, Rajeev Raman, Srinivasa Rao Satti
We consider the problem of preprocessing an array A[1..n] to answer range selection and range top-k queries. Given a query interval [i..j] and a value k, the former query asks for the position of the kth largest value in A[i..j], whereas the latter asks for the positions of all the k largest values in A[i..j]. We consider the encoding version of the problem, where A is not available at query time, and an upper bound kappa on k, the rank that is to be selected, is given at construction time. We obtain data structures with asymptotically optimal size and query time on a RAM model with word size Θ(lg n) : our structures use O(n lg kappa) bits and answer range selection queries in time O(1+ lg k / lg lg n) and range top-k queries in time O(k), for any k ≤ kappa.

History

Citation

Proceedings of (FSTTCS 2014) 34th Foundations of Software Technology and Theoretical Computer Science conference, 2014, in Leibniz International Proceedings in Informatics (LIPIcs).

Author affiliation

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

Source

FSTTCS the 34th Foundations of Software Technology and Theoretical Computer Science conference

Version

  • AM (Accepted Manuscript)

Published in

Proceedings of (FSTTCS 2014) 34th Foundations of Software Technology and Theoretical Computer Science conference

Publisher

Leibniz International Proceedings in Informatics (LIPIcs)

Copyright date

2014

Available date

2014-12-15

Publisher version

http://drops.dagstuhl.de/opus/volltexte/2014/4850/

Notes

The file associated with this record is embargoed until the date of the conference.

Temporal coverage: start date

2014-12-15

Temporal coverage: end date

2014-12-17

Language

en

Usage metrics

    University of Leicester Publications

    Categories

    Keywords

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC