Encodings for Range Selection and Top-k Queries
Roberto Grossi, John Iacono, Gonzalo Navarro, Rajeev Raman, and S. Srinivasa Rao.
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 <= k <= 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.