hide
Free keywords:
Computer Science, Data Structures and Algorithms, cs.DS
Abstract:
In this paper we consider various encoding problems for range queries on
arrays. In these problems, the goal is that the encoding occupies the
information theoretic minimum space required to answer a particular set of
range queries. Given an array $A[1..n]$ a range top-$k$ query on an arbitrary
range $[i,j] \subseteq [1,n]$ asks us to return the ordered set of indices
$\{l_1 ,...,l_k \}$ such that $A[l_m]$ is the $m$-th largest element in
$A[i..j]$. We present optimal encodings for range top-$k$ queries, as well as
for a new problem which we call range min-max, in which the goal is to return
the indices of both the minimum and maximum element in a range.
