TY - JOUR
T1 - Asymptotically optimal encodings of range data structures for selection and top-k queries
AU - Grossi, Roberto
AU - Iacono, John
AU - Navarro, Gonzalo
AU - Raman, Rajeev
AU - Satti, S. Rao
N1 - Funding Information:
Early partial versions of this article appeared in Proc. ESA 2013 and Proc. FSTTCS 2014.Grossiwas partially funded by MIUR PRIN 2012C4E3KT national research project; Navarro was funded in part by Millennium Nucleus Information and Coordination in Networks ICM/FIC P10-024F; Satti was partly supported by Basic Science Research Program through the National Research Foundation ofKorea (NRF) funded by the Ministry of Education, Science and Technology (Grant number 2012-0008241).
Publisher Copyright:
©2017 ACM.
PY - 2017/3
Y1 - 2017/3
N2 - Given 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 nlg k - O(n + klg k) bits of space,then,we design encodings using O(nlg k) bits,that is,asymptotically optimal up to constant factors,while preserving optimal query time.
AB - Given 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 nlg k - O(n + klg k) bits of space,then,we design encodings using O(nlg k) bits,that is,asymptotically optimal up to constant factors,while preserving optimal query time.
KW - Encoding data structures
KW - Range minimum queries
KW - Range search data structures
KW - Succinct data structures
UR - http://www.scopus.com/inward/record.url?scp=85017109865&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85017109865&partnerID=8YFLogxK
U2 - 10.1145/3012939
DO - 10.1145/3012939
M3 - Article
AN - SCOPUS:85017109865
SN - 1549-6325
VL - 13
JO - ACM Transactions on Algorithms
JF - ACM Transactions on Algorithms
IS - 2
M1 - 28
ER -