Asymptotically Optimal Encodings for Range Selection

Navarro, Gonzalo; Raman, Rajeev; Satti, Srinivasa Rao

doi:10.4230/LIPIcs.FSTTCS.2014.291

Document

Asymptotically Optimal Encodings for Range Selection

Authors Gonzalo Navarro, Rajeev Raman, Srinivasa Rao Satti

Part of: Volume: 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)
Part of: Series: Leibniz International Proceedings in Informatics (LIPIcs)
Part of: Conference: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS)
License: Creative Commons Attribution 3.0 Unported license
Publication Date: 2014-12-12

PDF

File

PDF

LIPIcs.FSTTCS.2014.291.pdf

Filesize: 474 kB
11 pages

Document Identifiers

DOI: 10.4230/LIPIcs.FSTTCS.2014.291
URN: urn:nbn:de:0030-drops-48502

Subject Classification

Keywords

Data Structures
Order Statistics
Succinct Data Structures
Space-efficient Data Structures

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

Abstract

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 k-th 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 Theta(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.

Cite As Get BibTex

Gonzalo Navarro, Rajeev Raman, and Srinivasa Rao Satti. Asymptotically Optimal Encodings for Range Selection. In 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 29, pp. 291-301, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014) https://doi.org/10.4230/LIPIcs.FSTTCS.2014.291

Author Details

Gonzalo Navarro

Rajeev Raman

Srinivasa Rao Satti

Questions / Remarks / Feedback

Feedback for Dagstuhl Publishing

Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail