Encoding Data Structures for Range Queries on Arrays

Efficiently processing range queries on arrays is a fundamental problem in computer science, with applications spanning diverse domains such as database management, computational biology, geographic information systems, and data analytics. A range query retrieves specific information about a contiguous segment of an array, such as the sum, minimum, maximum, or median of elements within a given range. Designing data structures to process such queries efficiently is critical, especially as datasets grow in size and complexity. The challenge lies in enabling fast query responses – often aiming for constant or logarithmic time – while minimizing the space overhead and preprocessing time required by the data structures.

Encoding data structures for range queries have emerged as a crucial area of research to address these challenges. Unlike traditional approaches that rely on augmenting the array with auxiliary structures or preprocessing, encoding-based methods focus on storing a compact representation of the data tailored specifically to the types of queries to be answered. These structures are designed to store only the information necessary for query resolution, eliminating the need to access the original array during query processing. The encoding data structures typically combine techniques from succinct/compressed data structures, combinatorial optimization and algorithmic design.

This survey aims to provide a comprehensive and structured overview of the key developments in the field of encoding data structures for range queries on arrays. We categorize the encoding solutions based on the specific types of range queries they support, such as range minimum/maximum queries, range top-$k$ queries, range mode queries, and range majority/minority queries. The survey article by Skala [51] from 2013 gives a detailed summary of various results for “range queries on arrays”. Thus we mainly focus on the new results since 2013, briefly summarizing the previous results.

Data structures can be classified into two categories: indexing and encoding data structures. For an indexing data structure, we preprocess the data and build an index so that subsequent queries can be answered efficiently by probing the index and the input data. On the other hand, for an encoding data structure, we preprocess the input data and build an encoding of the input so that subsequent queries can be answered by probing only the encoding (i.e., with no access to the input at query time). In this survey, we mainly focus on the results on encoding data structures, but occasionally mention a few results on indexing data structures for comparison. For many problems, the size of an encoding can be smaller than the size of the input, which is in fact the case for many range queries that we consider.

For example, given a query range, a range minimum query returns the minimum element within the query range. Range median, range mode, range selection and top-$k$, range mode and majority/minority queries are defined analogously. With this definition of range queries, one can reconstruct the input array by asking point queries with range that contains a single element, and hence the size of an encoding is at least the size of the input, and storing the input explicitly gives an optimal space encoding. To avoid this, we define the range queries as follows. For a query range, the range minimum query returns a position of the minimum element within the query range (and analogously for other range queries), instead of the value at the position. With this definition, one can obtain an encoding of size linear in bits for range minimum queries, which is asymptotically less than the space required to store the input array in the word RAM model.

In this article, we consider the encoding data structures for a 1D array $A[1,n]$, and a 2D array $A[1,m][1,n]$, where $m\le n$. We assume that the array indices start from 1. For 2D arrays, we use the term range to mean an rectangular range which is defined as a Cartesian product of a given set of intervals in each dimension. We assume a word RAM model with word-size $\mathrm{\Theta }(\log n)$ bits. For the encoding structures where we do not mention the query times, queries can be supported in polynomial time by essentially decoding the entire structure.

Given an input array and a query range, a range minimum query (RMQ) returns the position of the minimum element within the query range. From its wide applications (e.g., constructing an indexing structure on a string [15]), designing a data structure to answer RMQ has intensive attention from the community. For the 1D case, any encoding for RMQ requires at least $2n-o(n)$ bits due to its bijective relationship with the Cartesian tree of the input [53]. The best-known result for a worst-case input is the $(2n+o(n))$-bit data structure by Fisher and Heun that supports $O(1)$ query time¹¹1considering the $o(n)$-term, the current best result is Navarro and Sadakane’s $(2n+O(n/{(\frac{\log n}{t})}^t))$-bit data structure that supports queries in $O(t)$ time [45].. For earlier results, see [51].

When the input is highly compressible, there are some results whose space usages are parameterized based on the compressed size of the input while still supporting efficient query time. Here, compressibility is considered in two ways: (1) The compressibility of the input [18, 49, 2, 21], and (2) the compressibility of the Cartesian tree of the input [21, 43]. Note that data structures in (1) can access the input, as they maintain the input array in a compressed form. In contrast, the results in (2) cannot access to the input as they maintain the compressed Cartesian tree with some auxiliary structures for the query support.

There also has been progress on space-query time trade-off lower bounds for the problem under the cell-probe model, which measures query time by counting the number of memory cell accesses only. Liu and Yu showed that any data structure answering RMQ in $O(t)$ time requires at least $2n+O(n/{(\log n)}^{O(t^2{\log }^{2}t)})$ bits of space [42]. Later, Liu improved the space lower bound to $2n+O(n/{(\log n)}^{O(t{\log }^{2}t)})$ bits [41].

Range selection and range top-$k$ queries are natural extensions of the RMQ, defined as follows: Given a positive integer $k$ and a query range, a range selection query (denoted as sel-$k$) returns the position of the $k$-th largest value within the range of the input. Similarly, a range top-$k$ query (denoted as top-$k$) returns the positions of the $k^{\prime }$-largest values within the range for all $k^{\prime }\le k$. From these definitions, RMQ can be considered a special case of sel-$k$ or top-$k$ with $k=1$. There are two variations of top-$k$: (1) sorted top-$k$ reports the answers in sorted order, based on the corresponding values in the input, and (2) unsorted top-$k$ reports the answers in an arbitrary order. For 1D array, Gawrychowski and Nicholson [25] showed that the space lower bound for answering sorted and unsorted top-$k$ are the same within additive lower order terms when $k=o(n)$. Throughout this survey, we use top-$k$ to refer to the sorted one.

For $k=2$, Davoodi et al. [10] proposed a $(3.272n+o(n))$-bit data structure that can answer top-$2$ in $O(1)$ time. Their solution is based on the Cartesian tree of the input, combined with additional information to support the queries. Furthermore, they showed that at least $2.656n-O(\log n)$ bits are required to answer top-$2$.

For general $k$, the first non-trivial result was introduced by Grossi et al.[31]. This work is an extended journal version of two earlier conference papers published in 2013 [32] and 2014 [44]. They first gave a space lower bound result that at least $n\log k-O(n+k\log k)$ bits are necessary to answer sel-$k$ or top-$k$, even when the query range is restricted to being $1$-sided (i.e., a prefix of the input). Then using the concept of shallow cuttings [9], they design two $O(n\log k)$-bit data structures. These structures support: (1) sel-$k$ in $O(1+\log k^{\prime }/\log \log n)$ time, and (2) top-$k$ in $O(k^{\prime })$ time, for any $1\le k^{\prime }\le k$. Hence, both data structures use asymptotically optimal space. Moreover, the query time for (1) is also optimal for any data structures using $O(n\cdot polylog(n))$ space, as shown by the lower bound result of Jørgensen and Larsen [36]. However, when the query range is $1$-sided, they show that the time lower bound on range selection queries can be circumvented. Specifically, for $1$-sided sel-$k$, they proposed two data structures that (1) uses $n\log k+o(n\log k)+n$ bits and supports queries in any $\omega (1)$ time, or (2) uses $(1+ϵ)n\log k$ bits and supports queries in $O(1/ϵ)$ time, for any constant .

The space upper and lower bounds for answering top-$k$ from [31] were later improved by Gawrychowski and Nicholson [23]. They showed that at least $n\log k+n(k+1)\log (1+1/k)$ bits are necessary to answer top-$k$ and proposed an encoding scheme whose space usage is optimal up to lower-order additive terms. For instance, when $k=2$, their encoding uses $2.755n+o(n)$ bits of space, improving upon the result of Davoodi et al.[10]. In the extended version of their paper [25], they also presented a $(1.5n\log k-\mathrm{\Theta }(n))$-bit data structure that can answer top-$k$ in $poly(k\log n)$ time. See Table 4 for a summary of the results on data structures for top-$k$ in a 1D array.

The approximated selection query is to find the position of an element whose rank lies between $k-\alpha s$ and $k+\alpha s$ for a constant , where $s$ denotes the length of the query range. In the special case where $k=1/2$, the query is referred to as an approximate range median query. Bose et al. [4] introduced a data structure that uses $O(n\log n/\alpha )$ bits of space, which can answer approximate range median queries in $O(1)$ time. For general $k$, El-Zein et al. [13] proposed a data structure with size $O(n/{\alpha }^3)$ bits that also supports $O(1)$ query time. When $k$ is fixed, they showed that the size of the data structure can be reduced to $O(n/{\alpha }^2)$ bits while maintaining the same query time. Therefore, the result improves the space usage of [4] for approximated range median queries. Additionally, they showed that both data structures use asymptotically optimal space for constant $\alpha$ by proving an $\mathrm{\Omega }(n)$-bit encoding lower bound for approximate range median queries.

Jo et al. [34] studied the top-$k$ on an $m\times n$ 2D array with $m\le n$. For queries restricted to the range $[1,m]\times [1,j]$, they proposed an $O(\min nk\lg m,nm\lg k)$-bit encoding for sorted top-$k$ and an $O(\min nk\lg (m/k),nm\lg (k/m))$-bit encoding for unsorted top-$k$. This result implies a space gap between the encodings for sorted and unsorted top-$k$ in 2D, unlike the 1D case, even when $k=o(mn)$. For arbitrary rectangular query ranges, they presented an $(m\log \left(\genfrac{}{}{0pt}{}{(k+1)n}{n}\right)+2nm(m-1)+o(n))$-bit encoding to answer top-$k$. Compared to the $O(nm\log n)$-bit trivial encoding, which explicitly stores the input, their encoding uses less space when $m=o(\log n)$.

A mode of a multiset $S$ is an element of $S$ that occurs at least as frequently as any other element in $S$. In the range mode problem, we are given an array $A$ of $n$ elements which we can preprocess so as to answer range mode queries efficiently. Given a query range $(i,j)$, the range mode query returns any position, between $i$ and $j$, of a mode of the multiset $\{A[i],A[i+1],\mathrm{\cdots },A[j]\}$. Krizanc et al. [40] were the first to consider the data structure version of the range mode problem. They proposed two structures achieving different time-space tradeoffs: (i) a data structure that takes $O(n^{2-2ϵ})$ words and supports queries in $O(n^{ϵ}\log n)$ time, for any , and (ii) a data structures that takes $O(n^2\log \log n/\log n)$ words and supports range mode queries in $O(1)$ time. The space bound of the second structure was improved to $O(n^2/\log n)$ words by Petersen [47]. Subsequently, Petersen and Grabowski [48] improved both the tradeoffs to shave-off a log factor, to obtain the following results: (i) an $O(n^{2-2ϵ})$ space structure that supports queries in $O(n^{ϵ})$ time, for any , and (ii) an $O(n^2\log \log n/{\log }^{2}n)$ space structure that supports the queries in $O(1)$ time.

Greve et al. [30] showed that any data structure that uses $S$ memory cells of $w$ bits needs $\mathrm{\Omega }(\frac{\log n}{\log (Sw/n)})$ time to answer range mode queries. Chan et al. [7] designed a data structure that uses $O(n)$ words of space and answers range mode queries in $O(\sqrt{n/\log n})$ time. Also, by reducing the Boolean matrix multiplication problem to the range mode problem, they showed that any data structure for range mode must have either $\mathrm{\Omega }(n^{\omega /2})$ preprocessing time or $\mathrm{\Omega }(n^{\omega /2-1})$ query time in the worst case, where $\omega$ denotes the matrix multiplication exponent.

As all the above data structures use at least linear space, they can store the input as part of the data structure. One can improve the space usage significantly by considering approximate versions of the query as described in the next subsection.

Range majority and range minority queries are fundamental problems in data mining and theoretical computer science. They involve preprocessing a sequence such that, given a range $(i,j)$, one can efficiently determine elements that occur frequently (majority) or infrequently (minority) within the range. These problems are closely related to range mode queries, which aim to find the most frequent element but are computationally harder.