TY - GEN
T1 - Encodings for range selection and top-k queries
AU - Grossi, Roberto
AU - Iacono, John
AU - Navarro, Gonzalo
AU - Raman, Rajeev
AU - Rao, Satti Srinivasa
PY - 2013
Y1 - 2013
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84884335118&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84884335118&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-40450-4_47
DO - 10.1007/978-3-642-40450-4_47
M3 - Conference contribution
AN - SCOPUS:84884335118
SN - 9783642404498
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 553
EP - 564
BT - Algorithms, ESA 2013 - 21st Annual European Symposium, Proceedings
T2 - 21st Annual European Symposium on Algorithms, ESA 2013
Y2 - 2 September 2013 through 4 September 2013
ER -