###
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*.