Optimal Encodings for Range Min-Max and Top-k

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] ⊆ [1, n] asks us to return the ordered set of indices {`1,..., `k} such that A[`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.