Please use this identifier to cite or link to this item:
Full metadata record
DC FieldValueLanguage
dc.contributor.authorGrossi, Roberto-
dc.contributor.authorIacono, John-
dc.contributor.authorNavarro, Gonzalo-
dc.contributor.authorRaman, Rajeev-
dc.contributor.authorSatti, S. Rao-
dc.identifier.citationACM Transactions on Algorithms (TALG), 2017, 13(2)en
dc.description.abstractGiven an array A[1, n] of elements with a total order, we consider the problem of building a data structure that solves two queries: (a) selection queries receive a range [i, j] and an integer k and return the position of the kth largest element in A[i, j]; (b) top-k queries receive [i, j] and k and return the positions of the k largest elements in A[i, j]. These problems can be solved in optimal time, O(1 + lg k/ lg lg n) and O(k), respectively, using linear-space data structures. We provide the first study of the encoding data structures for the above problems, where A cannot be accessed at query time. Several applications are interested in the relative order of the entries of A, and their positions, rather their actual values, and thus we do not need to keep A at query time. In those cases, encodings save storage space: we first show that any encoding answering such queries requires n lg k − O(n + k lg k) bits of space; then, we design encodings using O(n lg k) bits, that is, asymptotically optimal up to constant factors, while preserving optimal query time.en
dc.publisherAssociation for Computing Machinery (ACM)en
dc.rightsCopyright © 2017, Association for Computing Machinery (ACM). Deposited with reference to the publisher’s open access archiving policy.en
dc.titleAsymptotically Optimal Encodings of Range Data Structures for Selection and Top-k Queriesen
dc.typeJournal Articleen
pubs.organisational-group/Organisation/COLLEGE OF SCIENCE AND ENGINEERINGen
pubs.organisational-group/Organisation/COLLEGE OF SCIENCE AND ENGINEERING/Department of Computer Scienceen
Appears in Collections:Published Articles, Dept. of Computer Science

Files in This Item:
File Description SizeFormat 
paper.pdfPost-review (final submitted author manuscript)536.53 kBUnknownView/Open

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