Please use this identifier to cite or link to this item:
Title: Encodings for range selection and top-k queries
Authors: Grossi, Roberto
Iacono, John
Navarro, Gonzalo
Raman, Rajeev
Rao, S. Srinivasa
First Published: 2013
Presented at: 21st Annual European Symposium, Sophia Antipolis, France, September 2-4, 2013.
Publisher: Springer Verlag
Citation: Algorithms – ESA 2013, Lecture Notes in Computer Science, 8125 LNCS, pp. 553-564
Abstract: We study the problem of encoding the positions the top-k elements of an array A[1..n] for a given parameter 1 ≤ k ≤ n. Specifically, for any i and j, we wish create a data structure that reports the positions of the largest k elements in A[i..j] in decreasing order, without accessing A at query time. This is a natural extension of the well-known encoding range-maxima query problem, where only the position of the maximum in A[i..j] is sought, and finds applications in document retrieval and ranking. We give (sometimes tight) upper and lower bounds for this problem and some variants thereof.
DOI Link: 10.1007/978-3-642-40450-4_47
ISSN: 0302-9743
ISBN: 978-3-642-40449-8
eISSN: 1611-3349
Version: Post-print
Status: Peer-reviewed
Type: Conference Paper
Rights: Copyright © 2013, Springer Verlag. Deposited with reference to the publisher’s archiving policy available on the SHERPA/RoMEO website.
Appears in Collections:Conference Papers & Presentations, Dept. of Computer Science

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

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