Indexing and Encoding Arrays for Element Distinctness Queries

Given an array $A$ of $n$ elements drawn from an alphabet $\mathrm{\Sigma }$, let $A[l,r]$ denote the subarray of $A$ from position $l$ to $r$. A range query $q_A(l,r,\mathrm{\cdots })$, for some (and possibly additional parameters “$\mathrm{\cdots }$”), is any function whose value depends only on the subarray $A[l,r]$ (and on the additional parameters, if any). Prominent examples of range queries include: range minimum queries, defined as ${\text{RMQ}}_A(l,r)={argmin}_{l\le i\le r}\{A[i]\}$, which return the position of the minimum element in $A[l,r]$ when $\mathrm{\Sigma }$ is totally ordered [8]; rank queries, defined as ${\text{rank}}_A(l,r,c)=|\{i:l\le i\le r\wedge A[i]=c\}|$ for some $c\in \mathrm{\Sigma }$, which count the occurrences of the symbol $c$ in $A[l,r]$ [14]; and range mode queries, which return the most frequent element in $A[l,r]$ [17]. Many other examples have been studied in the literature [24]. We are interested in the data structure perspective of range queries, i.e., given a static array $A$ and a function $q_A$ (or simply $q$ in the following), the goal is to build a compact data structure $𝒟(A,q)$ that allows us to answer queries efficiently.

We introduce a new type of query which, despite its fundamental nature, to the best of our knowledge appears not to have been previously studied from the data structure perspective: element distinctness queries. Formally, a query ${\text{All-Distinct}}_A(l,r)$ returns true if all elements in $A[l,r]$ are distinct, and false otherwise.

In an algorithmic setting, where the task is to detect whether an array contains any duplicate elements, this is a well-studied problem; see [25] for recent progress in that context.

We argue that it is worth considering this problem in the array query setting. When $A$ is the document array [20] of a text collection, an index returns the suffix array interval $[l,r]$ corresponding to a given pattern $P$. Asking whether $P$ occurs exactly once in each text then corresponds precisely to a ${\text{All-Distinct}}_A(l,r)$ query, which could, for example, provide insight into the biological function of a queried DNA fragment.

There are two models of range query problems [6], depending on whether the input array $A$ is available at query time (indexing model) or not (encoding model). In the indexing model, some space for the data structure $𝒟$ can potentially be saved, as the query algorithm may compensate for missing information by consulting $A$ when answering the queries. However, since access to $A$ is required at query time, the total space usage, which is $|A|+|𝒟|$ bits, can never be sublinear in the space needed to store $A$ itself.

This contrasts with the encoding model, where the data structure $𝒟$ must be constructed so that queries can be answered without consulting $A$. Any encoding data structure ${𝒟}_{\text{E}}$ is automatically also an indexing data structure. Conversely, an indexing data structure ${𝒟}_{\text{I}}$ can always be converted to an encoding data structure by storing ${𝒟}_{\text{I}}$ together with a copy of $A$. Consequently, distinguishing between the two models is meaningful only if there exist indexing data structures that use less space than the best encoding data structures, and if encoding data structures can achieve space usage sublinear in $|A|$.

As for range minimum queries [8], we show that this is indeed the case for All-Distinct-queries. Specifically, in Sect. 2 we prove the following result, which, for the sake of generality, is stated in terms of parameters $T_{dist}(b,\sigma )$ and $S_{dist}(b,\sigma )$ denoting the time and space complexity of online algorithms for the element distinctness problem:

Let us give two concrete instantiations of the theorem for the choice of $b=\mathrm{\Theta }(\log n)$, which yields an index using $O(n\log \log n/\log n)=o(n)$ bits of space. First, assuming that $\sigma =O(n\log \log n/{\log }^{2}n)$, we can solve the element distinctness problem using counting sort in $T_{dist}(b,\sigma )=O(\log n)$ time and $S_{dist}(b,\sigma )=O(n\log \log n/\log n)$ bits of working space, which does not exceed the space of the index. Second, without any restriction on $\sigma$, one can use comparison based sorting to solve element distinctness queries in $T_{dist}(b,\sigma )=O(\log n\log \log n)$ time using only a negligible amount $S_{dist}(b,\sigma )=O({\log }^{2}n)$ bits of working space. We refer to [25] and references therein for other space-time trade-offs for the element distinctness problem. Using comparison sort, we can actually set the block size to any $b=\omega (1)$ to achieve sublinear space and $O(b\log b)$ query time. For instance, with $b=\frac{{\log }^{[k]}n}{{\log }^{[k+1]}n}$ for a positive constant integer $k$, where ${\log }^{[k]}n$ denotes $k$ iterations of the logarithm, the space of the index is $O(\frac{n{({\log }^{[k+1]}n)}^2}{{\log }^{[k]}n})=o(n)$ bits, and the query time is $O({\log }^{[k]}n)$.

Moving to the encoding model, in Sect. 3, we begin by showing the following result:

We then consider restricted alphabet sizes, where we refine Thm. 2 as follows:

Interpreting the term $\log r_{\sigma }$ as a function of $\sigma$, we observe that , therefore , and hence the leading term in the space usage of Thm. 3 is never larger than $2n$ bits. Some special cases for small alphabet sizes ($\sigma =2,3,4)$ can be computed explicitly as $n$, $2n\log ((1+\sqrt{5})/2)=1.388n$, and $n\log 3=1.585n$, respectively. Interestingly, these are the same values for range minimum queries on restricted alphabets [16].

Finally, we note that all our results hold in the transdichotomous word-RAM model, where the word size $w$ satisfies $w=\mathrm{\Theta }(\log n)$, and arithmetic as well as bitwise operations on $w$ bits are performed in constant time. Additionally, our results also require the alphabet to be linearly sortable (e.g., characters drawn from a universe of size $n^{O(1)}$). This assumption is necessary to compactify the alphabet to $[1,\sigma ]$ in linear time; otherwise, we would violate the natural $O(n\log n)$ lower bound for duplicate detection in in the comparison model [18].

In the indexing version of the All-Distinct problem, the data structure is allowed to access the input array while answering queries. In this section, we design an index whose space usage and query time can be tuned based on an input parameter $b\ge 1$. To this end, we first introduce two sequences that form the basis of our solution:

Both $P_A$ and $N_A$ are monotone, with $P_A$ being non-decreasing and $N_A$ being non-increasing. Moreover, by the pigeonhole principle, any range of length greater than $\sigma$ must contain at least one duplicate. It follows that for each , we have $\max \{0,i-\sigma +1\}\le P_A[i]\le i$ and similarly $i\le N_A[i]\le \min \{n-1,i+\sigma -1\}$.

Constructing either of these two sequences can be easily done in $O(n)$ time and $O(\sigma \log n)$ bits of space. We describe the procedure for $P_A$, but the same idea applies to the construction of $N_A$. We compute $P_A[i]$ for all in increasing order, starting with $P_A[0]=0$. We maintain an auxiliary array $C[0,\sigma -1]$, initialized with negative values, where $C[k]$ stores the index of the last occurrence of symbol $k$ in the current range $[i,j]$. When computing $P_A[i]$, we can inductively assume that $P_A[i-1]$ has already been computed. If , we set $P_A[i]$ to $P_A[i-1]$, as the new symbol $A[i]$ does not induce a duplicate in $A[P_A[i-1],i]$. Otherwise, we set $P_A[i]$ to $C[A[i]]+1$, which is the minimal index $j$ such that $A[i]$ is not repeated in $A[j,i]$. In all cases, we update $C[A[j]]$ to $j$.

Having access to either $P_A$ or $N_A$ is already sufficient to answer any $\text{All-Distinct}(l,r)$ query in $O(1)$ time: because of Def. 4, the answer is false if $P_A[r]>l$, and true otherwise (equivalently, one may check whether ). However, even though $P_A$ and $N_A$ can certainly be stored in fewer than $n\lceil \log n\rceil$ bits, it is impossible to use less than (roughly) a linear number of bits without having access to $A$ (see Sect. 3 for details). Therefore, we proceed to show how this can be achieved in the indexing setting.

Our index is obtained by first partitioning the input array $A$ into $\lceil n/b\rceil$ blocks of size . For each , we sample the array $P_A$ at position $(i+1)b-1$, i.e., the last element of the $i$-th block, and store the resulting value in a separate array $S_{P_A}$. Similarly, for the same values of $i$, we sample the array $N_A$ at position $ib$, i.e., the first element of the $i$-th block, storing these values in another array $S_{N_A}$. After collecting these samples, the full arrays $P_A$ and $N_A$ are discarded, and only their sampled versions are used to answer queries.

$S_{P_A}$ and $S_{N_A}$ both require $\frac{n}{b}\lceil \log n\rceil$ bits each if stored plainly, but we can save space using ideas similar to Elias-Fano codes [21, §3.4.3]: Let us now focus on $S_{P_A}$, as the same considerations apply to $S_{N_A}$. For each , we compute the integer division $S_{P_A}[i]/b$, and store the quotient in $Q_{P_A}[i]$, and the remainder in $R_{P_A}[i]$. $Q_{P_A}$ is again monotonically increasing, with each $0\le Q_{P_A}[i]\le n/b$, hence by encoding the differences between consecutive elements in negated unary and augmenting the resulting binary sequence with ${\text{select}}_1$ support [15, 13] we can access each element of $Q_{P_A}$ in $O(1)$ time while using $\frac{2n}{b}+o(\frac{n}{b})$ bits of space. $R_{P_A}$ is stored plainly using $\frac{n}{b}\lceil \log b\rceil$ bits, and supports $O(1)$ time access. Each $S_{P_A}[i]$ can then be reconstructed in $O(1)$ time as $b\cdot Q_{P_A}[i]+R_{P_A}[i]$. Overall, this encoding for both $S_{P_A}$ and $S_{N_A}$ requires $\frac{2n}{b}(2+\log b)+o(\frac{n}{b})$ bits of space.

Answering queries with our index is straightforward. Given a query $\text{All-Distinct}(l,r)$, we first split the range $[l,r]$ into three parts: $[l,l^{\prime }-1]$, $[l^{\prime },r^{\prime }]$, and $[r^{\prime }+1,r]$, where $[l^{\prime },r^{\prime }]$ is the maximal subrange of $[l,r]$ that perfectly aligns with full blocks of size $b$ in $A$. Using the same idea as for answering queries with either $P_A$ or $N_A$, we check in constant time whether the aligned portion $[l^{\prime },r^{\prime }]$ contains any duplicates by verifying if $S_{P_A}[r^{\prime }/b]>l$ or . If this test fails, the answer to the query is immediately false. However, this is insufficient to guarantee uniqueness over the entire range $[l,r]$. Indeed, an element in $A[l,l^{\prime }-1]$ may also appear in $A[r^{\prime }+1,r]$, and such duplicates are not yet detected by simply verifying the previous condition. Therefore, $A[l,l^{\prime }-1]\cup A[r^{\prime }+1,r]$ must be checked for duplicates, which is an $O(b)$-sized instance of the element distinctness problem.

We now consider All-Distinct queries in the encoding model, in which the underlying array $A$ cannot be accessed at query time. We first consider the general case, developing upper and lower bounds that are independent of the alphabet size $\sigma$ (Thm. 2). We then focus on restricted alphabets, where tighter bounds can be obtained (Thm. 3).

We introduced a new type of range query on arrays, with potential applications in text indexing as well as other algorithmic realms. Our algorithms build on techniques that are inspired by range minimum queries [7, 8], but needed substantial new ideas and adaptations to work for All-Distinct. We note that in cases where an All-Distinct query returns a negative answer, our algorithms can be easily modified to report the position of a duplicate in the query range, if desired. Future research directions include: proving a space-time trade-off lower bound in the indexing model [1]; extending the techniques to higher dimensional arrays [2]; considering upper and lower bounds for random instances [19]; compressing the data structures [9, 12]; learning from the distribution of the data [5]; or exploring relaxed variants, such as parameterized queries that return true if the query range contains at most $k$ repeated elements, with $k$ specified either at preprocessing or at query time. So far, we have considered only the simplest case of queries testing the distinctness of values in a range. More challenging problems include deciding whether a unique element exists in the query range, as well as counting or reporting distinct or repeated elements, similarly to [11].