|
Title |
Encodings for Range Selection and Top-k Queries |
|
Authors |
Roberto Grossi, John Iacono, Gonzalo Navarro, Rajeev Raman, S. Srinivasa Rao |
|
Publication date |
2013 |
|
Abstract |
We study the problem of encoding the positions of the k-th maximum and the top-k elements, for all possible ranges of an array A[1..n] and a given parameter 1 \le k \le n. For any i and j, our queries quickly report the position of the k-th largest element in the range, and the positions of the largest k elements in A[i..j] in decreasing order. This is a natural extension of the well-known 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 upper and lower bounds for several variants of our problem, under the assumption that our proposed data structures (i) do not access A during the queries and (ii) occupy a number of bits that depends on n and k, and is independent of the number of bits required to store the individual elements in A. |
|
Pages |
553-564 |
|
Conference name |
Annual European Symposium on Algorithms |
|
Publisher |
Springer-Verlag (Berlin/Heidelberg, Germany) |
|
Reference URL |
|
