License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2014.291
URN: urn:nbn:de:0030-drops-48502
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4850/
Go to the corresponding LIPIcs Volume Portal

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

Asymptotically Optimal Encodings for Range Selection

pdf-format:
26.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{navarro_et_al:LIPIcs:2014:4850,
  author =	{Gonzalo Navarro and Rajeev Raman and Srinivasa Rao Satti},
  title =	{{Asymptotically Optimal Encodings for Range Selection}},
  booktitle =	{34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)},
  pages =	{291--301},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-77-4},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{29},
  editor =	{Venkatesh Raman and S. P. Suresh},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4850},
  URN =		{urn:nbn:de:0030-drops-48502},
  doi =		{10.4230/LIPIcs.FSTTCS.2014.291},
  annote =	{Keywords: Data Structures, Order Statistics, Succinct Data Structures, Space-efficient Data Structures}
}

Keywords: Data Structures, Order Statistics, Succinct Data Structures, Space-efficient Data Structures
Collection: 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)
Issue Date: 2014
Date of publication: 12.12.2014

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI