Please use this identifier to cite or link to this item: http://hdl.handle.net/2381/29193
Title: Asympotically optimal encodings for range selection
Authors: Navarro, Gonzalo
Raman, Rajeev
Satti, Srinivasa Rao
First Published: 17-Dec-2014
Presented at: FSTTCS the 34th Foundations of Software Technology and Theoretical Computer Science conference
Start Date: 15-Dec-2014
End Date: 17-Dec-2014
Publisher: Leibniz International Proceedings in Informatics (LIPIcs)
Citation: Proceedings of (FSTTCS 2014) 34th Foundations of Software Technology and Theoretical Computer Science conference, 2014, in Leibniz International Proceedings in Informatics (LIPIcs).
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 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.
DOI Link: 10.4230/LIPIcs.FSTTCS.2014.291
Links: http://drops.dagstuhl.de/opus/volltexte/2014/4850/
http://hdl.handle.net/2381/29193
Version: Post-print
Status: Peer-reviewed
Type: Conference Paper
Rights: Copyright © the authors, 2014. This is an open-access article distributed under the terms of the Creative Commons Attribution License ( http://creativecommons.org/licenses/by/3.0/ ), which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.
Description: The file associated with this record is embargoed until the date of the conference.
Appears in Collections:Conference Papers & Presentations, Dept. of Computer Science

Files in This Item:
File Description SizeFormat 
paper-88.pdfPost-review (final submitted)519.53 kBAdobe PDFView/Open


Items in LRA are protected by copyright, with all rights reserved, unless otherwise indicated.