Faster Linear-Space Data Structures for Path Frequency Queries

Krizanc et al. [13] presented $O(n)$-space data structures that support range mode queries in $O(\sqrt{n}\log \log n)$ time on arrays and $O(\sqrt{n}\log n)$ time on trees. Chan et al. [6] achieved $o(\sqrt{n})$ query time with an $O(n)$-space data structure that supports queries in $O(\sqrt{n/w})\subseteq O(\sqrt{n/\log n})$ time on arrays. Durocher et al. [10] present an $O(n)$ space data structure supporting path mode queries on trees in $O(\log \log n\sqrt{n/w})$ time. Durocher et al. [10] ask whether the $\log \log n$ gap between the path mode query time on trees and the range mode query time on arrays can be closed. In this paper, we present the first $O(n)$ space data structure that supports path mode queries in $O(\sqrt{n/w})\subset o(\log \log n\sqrt{n/w})$ query time, thus eliminating the gap between path mode and range mode query times.

In the context of the least frequent element problem, Chan et al. [7] presented an $O(n)$-space data structure that supports range least frequent element queries on arrays in $O(\sqrt{n})$ time. Durocher et al. [10] improve the range least frequent element query time down to $O(\sqrt{n/w})$, and designed the first path least frequent element query data structure for trees, with an $O(\log \log n\sqrt{n/w})$ query time. In our paper, we present the first linear-space data structure that supports path least frequent element queries on trees in $O(\sqrt{n/w})$ time, thus also closing the $\log \log n$ gap between the array and tree query times for this problem. A history of previous best query times, achieved by linear-space data structures for mode queries and least frequent element queries, is presented in Tables 1, 2.

In their work, Durocher et al. [10] present a linear-space data structure that can answer path $\alpha$-minority queries on trees in $O({\alpha }^{-1}\log \log n)$ time, with $\alpha$ specified at query time. The path $\alpha$-minority query for a tree path $(u,v)$ asks to report any color that occurs at most an $\alpha$ fraction of the tree path between nodes $u$ and $v$. We prove that by applying a simple randomized algorithm with success probability $\ge 1/2$, their linear-space data structure can support $\alpha$-minority queries in $O({\alpha }^{-1})$ time, improving on the previous $O({\alpha }^{-1}\log \log n)$ query time. A history of query times achieved by linear-space data structures for $\alpha$-minority is given in Table 3.

An instance of our problem consists of an array of integers $A$ (referred to as the “array of colors”) and an integer function $g$. Let $n=|A|$. We assume that $1\le A[i]\le n$. If $A$ does not fulfill this requirement, $A$ can be transformed in $O(n\log n)$ time to an array $A^{\prime }$ with values compressed to the interval $\{1,\mathrm{\dots },n\}$.

The starting point of our study was the range mode function. We developed our data structure using only a subset of the properties of the range and path mode functions. We require $g$ to satisfy the following constraints, all of which are shared by the range mode function:

1. 1.

   Domain: The function $g(i,j,c)$ takes three integer arguments, where $1\le i\le j\le n$ are indices of $A$, and $c$ is a color present in the subarray $A[i\mathrm{\dots }j]$.

2. 2.

   Output: $g$ produces an integer output that fits into a single machine word.

3. 3.

   Range Contraction: For any valid input $(i,j,c)$,

   $$g(i,j,c)=g(i^{\prime },j^{\prime },c)$$

   where $i^{\prime }$ and $j^{\prime }$ are the minimum and maximum indices, respectively, such that $i\le i^{\prime }\le j^{\prime }\le j$ and $A[i^{\prime }]=A[j^{\prime }]=c$. In other words, the value of $g$ depends only on the range spanned by the occurrences of $c$ within the query interval.

4. 4.

   Oracle Complexity: We assume $g$ can be computed efficiently given a contracted range. Specifically, computing $g(i,j,c)$ such that $A[i]=A[j]=c$ takes $O(1)$ time. This computation may use an additional $O(n)$-space static data structure.

The Range Maximum $g$-value Color problem is to preprocess $A$ and the function $g$ to efficiently answer queries of the following form:

Given two indices $i,j$ of $A$, determine: $\arg {\max }_{c\in A[i\mathrm{\dots }j]}\{g(i,j,c)\}$

In other words, determine any single color $c$ corresponding to the maximum value of $g(i,j,c)$.

This problem generalizes naturally to trees. Instead of an array, we are given a rooted, node-colored tree $𝒯$ and a function $g$ defined on tree paths. An input to $g$ consists of a triple $(u,v,c)$, where $u,v$ are nodes in $𝒯$ and $c$ is a color occurring on the simple path $P(u,v)$. From now on, we will consider $𝒯$ to be rooted at node $1$.

The properties of $g$ remain analogous. Crucially, the Range Contraction property (Property 3) translates as follows:

where $u^{\prime }$ is the node on $P(u,v)$ closest to $u$ such that $𝒯[u^{\prime }]=c$, and $v^{\prime }$ is the node on $P(u,v)$ closest to $v$ such that $𝒯[v^{\prime }]=c$, where $𝒯[u]$ denotes the color of node $u$ in the tree $𝒯$.

We refer to this generalized problem as the Path Maximum $g$-value Color problem. This is the main problem we focus on in our work. In the following sections, we present a linear-space data structure supporting path maximum $g$-value color queries in $O(\sqrt{n/w})$ time, requiring $O(n\sqrt{nw})$ preprocessing time.

To motivate why this abstract definition is interesting in its own right, we introduce the Range Maximum Sum Color problem. Given a color array $A$ and a cost array $V$, we wish to find the color in a range $A[i\mathrm{\dots }j]$ that maximizes the sum of its associated costs. Formally:

This is a specific instance of the maximum $g$-value color problem, as the summation function satisfies all properties of $g$ (specifically, the sum of costs for color $c$ in range $[i,j]$ is identical to the sum in the contracted range $[i^{\prime },j^{\prime }]$).

This problem, again, naturally generalizes to trees; thus, we obtain the Path Maximum Sum Color problem. By using the virtual tree data structure, and Lemma 2 presented in Section 3, we can easily verify that:

where $lca$ is the lowest common colored ancestor of $u_c$ and $v_c$ (which requires $𝒯$ to be rooted), $u_c,v_c$ are both $c$-colored nodes, and $r_c$ is the root of the virtual tree of color $c$. We can verify that $g(u_c,v_c,c)$ can be computed in $O(1)$ time using relation 1 if we store for each $u_c$ the values $g(u_c,r_c,c)$ in a table of size $O(n)$.

Both on arrays and on trees, the Maximum Sum Color problem acts as a generalization for both the Mode problem (where $V[k]=1$ for all $k$) and the Least Frequent Element problem (where $V[k]=-1$ for all $k$, allowing us to maximize the negated sum).

We conclude this section by outlining the difficulty hierarchy. We focus on solving the most general variant: the Path Maximum $g$-value Color problem on trees. We present a linear-space data structure for this problem with a query time of $O(\sqrt{n/w})$. Remarkably, this matches the query time of the fastest known data structure for the range mode query problem (Chan et al. [6]), which corresponds to the simplest case in our hierarchy.

We define virtual trees, which are essential for our data structure.

To ensure ${𝒱}_c$ is a single connected tree (rather than a forest), we introduce a virtual root node $r_c$ for each color $c$. If a node $v$ of color $c$ has no ancestors of color $c$ in $𝒯$, we set its parent in ${𝒱}_c$ to be $r_c$.

It is possible to construct all virtual trees ${𝒱}_c$ for all colors $c$ in $O(n)$ total time using a single depth-first traversal of $𝒯$. Since the node sets for each color form a partition of the colored nodes in $𝒯$, the total space required is linear, $O(n)$. We defer the algorithm for computing all the virtual trees ${𝒱}_c$ to the full version of this paper, available as a preprint on arXiv [14].

By applying standard LCA and Level Ancestor structures (Lemmas 1 and 2) to these virtual trees, we obtain the following corollary:

For our specific data structure, we employ a $3$-level partition of $𝒯$. We assume the first blocking factor $t_1$ is provided as a parameter. We then define the higher-level factors as follows:

During the preprocessing phase, we compute the associated structures $M_{t_i}$, ${𝒯}_{t_i}$, and ${ℬ}_{t_i}$ for $1\le i\le 3$. Specifically, we construct the full block partitions ${ℬ}_{t_i}$ using the hierarchical method described in Corollary 7. Based on the established results, this entire preprocessing step requires $O(n\log n)$ time.

To efficiently identify these candidate nodes, we decompose the query based on the hierarchy of blocks defined in Section 4. We decompose the problem into disjoint subtasks by partitioning the set of distinct colors present on the query path. Each subtask identifies a unique subset of colors based on their presence or absence in the hierarchical blocks surrounding $i$ and $j$.

Let $C_{path}=C(P(i,j))$ denote the set of all distinct colors present on the query path. For any block $B$, let $C(B)$ denote the set of distinct colors present in that block.

We define the complement of a block’s color set with respect to the entire tree. Let $𝒰$ be the universe of all distinct colors in the tree $𝒯$. We define:

This represents the set of all colors in the tree that are not present in block $B$.

The set of path colors $C_{path}$ is partitioned into the following disjoint subsets $C_1,\mathrm{\dots },C_{10}$ using intersection operations on these color sets:

• $\mathrm{■}$

  1. The Global Colors: $C_1=C_{path}\cap \overline{C(B_3(i))}\cap \overline{C(B_3(j))}$.

  Colors on the path that are not present in the Level 3 blocks of either endpoint.

• $\mathrm{■}$

  2. The Level 3 Ascent: $C_2=C_{path}\cap C(B_3(i))\cap \overline{C(B_2(i))}\cap \overline{C(B_3(j))}$.

  Colors on the path that are in $i$’s Level 3 block, but not in $i$’s Level 2 block or $j$’s Level 3 block.

• $\mathrm{■}$

  3. The Level 2 Ascent: $C_3=C_{path}\cap C(B_2(i))\cap \overline{C(B_1(i))}\cap \overline{C(B_3(j))}$.

  Colors on the path that are in $i$’s Level 2 block, but not in $i$’s Level 1 block or $j$’s Level 3 block.

• $\mathrm{■}$

  4. The Level 3 Descent: $C_4=C_{path}\cap C(B_3(j))\cap \overline{C(B_2(j))}\cap \overline{C(B_3(i))}$.

  Symmetric to $C_2$.

• $\mathrm{■}$

  5. Level 3 Intersection: $C_5=C_{path}\cap C(B_3(i))\cap C(B_3(j))\cap \overline{C(B_2(i))}\cap \overline{C(B_2(j))}$.

  Colors on the path present in both Level 3 blocks, but in neither Level 2 block.

• $\mathrm{■}$

  6. Mixed Intersection: $C_6=C_{path}\cap C(B_2(i))\cap C(B_3(j))\cap \overline{C(B_1(i))}\cap \overline{C(B_2(j))}$.

  Colors on the path present in $i$’s Level 2 block and $j$’s Level 3 block, excluding inner blocks.

• $\mathrm{■}$

  7. The Level 2 Descent: $C_7=C_{path}\cap C(B_2(j))\cap \overline{C(B_1(j))}\cap \overline{C(B_3(i))}$.

  Symmetric to $C_3$.

• $\mathrm{■}$

  8. Mixed Intersection: $C_8=C_{path}\cap C(B_3(i))\cap C(B_2(j))\cap \overline{C(B_2(i))}\cap \overline{C(B_1(j))}$.

  Symmetric to $C_6$.

• $\mathrm{■}$

  9. Level 2 Intersection: $C_9=C_{path}\cap C(B_2(i))\cap C(B_2(j))\cap \overline{C(B_1(i))}\cap \overline{C(B_1(j))}$.

  Colors on the path present in both Level 2 blocks, excluding both Level 1 blocks.

• $\mathrm{■}$

  10. Local Colors: $C_{10}=C_{path}\cap \left(C(B_1(i))\cup C(B_1(j))\right)$.

  Colors on the path present in the smallest (Level 1) blocks of either endpoint.

In the subsequent analysis, we will omit the subtasks marked as symmetric to others (e.g., $C_4$, $C_7$, $C_8$), as their solutions are algorithmically identical to their counterparts, differing only in orientation.

For each of the subtasks 4-9, we will identify sets of candidate nodes of size $O(t_2)$, together with the corresponding endpoints $l,r$, and add them to the set $S_2$. For subtasks $1-3$ and $10$, we will identify sets of candidates of size $O(t_1)$ or $O(1)$, and add them to $S_1$. At the end, we process the sets $S_2$ and $S_1$, in time $O(|S_2|)=O(t_2)$ and $O(|S_1|\cdot \log \log n)=O(t_1\cdot \log \log n)$, respectively, and return the color with the largest $g$-value. Since $t_1\log \log n=t_2$, processing $S_1$ and $S_2$ takes $O(t_2)$ in total.

We precompute a table $T$ of size $O\left({(n/t_3)}^2\right)$, indexed by the identifiers of the blocks in ${ℬ}_{t_3}$. For every pair of blocks $B_u,B_v\in {ℬ}_{t_3}$ with representatives $u,v$, the entry $T[u][v]$ stores the color $c$ that maximizes $g(u,v,c)$, restricted to colors appearing on the path $P(u,v)$ but not in $C(B_u)\cup C(B_v)$. During a query, we identify the blocks $u=B_3(i)$ and $v=B_3(j)$, retrieve the candidate $c=T[u][v]$ in $O(1)$ time, and add it to the primary candidate set $S_1$. The table construction requires $O(n\cdot (n/t_3))$ preprocessing time and $O\left({(n/t_3)}^2\right)$ space, measured in words.

We employ a lookup table $T$ of size $O(\frac{n}{t_2}\cdot \frac{n}{t_3})$, indexed by pairs $(u,v)$ representing a Level 2 block and a Level 3 block. The entry $T[u][v]$ stores the relative index (using $O(\log \log n)$ bits) of a specific Level 1 block (or $t_1$-node) inside $B_3(i)$ that contains at least one occurrence of the optimal color. During a query, we iterate through every distinct color $c^{\prime }$ in this retrieved $t_1$-node’s subtree and add each to $S_1$.

This solution is analogous to Subtask 2. We use a table $T$ of size $O(\frac{n}{t_1}\cdot \frac{n}{t_3})$. For a pair of blocks $B_u$, $B_v$ (Level 1 and Level 3), $T[u][v]$ stores the index of a $t_1$-node inside $B_2(u)$ containing the optimal color. All colors in that $t_1$-node are added to $S_1$.

To efficiently solve the intersection subtasks, we require advanced data structures that allow us to locate specific color occurrences within the block hierarchy in constant time. We refer to trees with size bounded by $s=\frac{\log n}{8\log \log n}$ as small trees.

We apply a stratified blocking approach. We define a sequence of blocking factors $s_0,\mathrm{\dots },s_{|s|}$ such that $s_0=t_3$, $s_{|s|}=t_2$, and $s_{k+1}=t_2\cdot {(\log (s_k/t_2))}^2$. Note that $|s|=O({\log }^{\ast }(t_3/t_2))$.

For each blocking factor $s_k$, let ${ℬ}_{s_k}$ be the set of $s_k$ blocks which partitions $V(𝒯)$. For an $s_k$ block $B\in {ℬ}_{s_k}$, let $L_B$ denote the list of all nodes from $V(𝒯)$, contained inside block $B$, ordered in increasing order of the node index. We construct tables $T_k$ for each level $s_k$. For every configuration of blocks $(B_{s_k}(i),B_{s_k}(j))$, we store the approximate position (using the most significant $2\log (s_k/t_2)$ bits) of the optimal color $c$ within the linearized list of nodes of the blocks $B_{s_k}(i),B_{s_k}(j)$. The total space required is:

where $r_k=s_k/t_2$. The query iterates through $O(t_2)$ candidate colors suggested by these tables. For each candidate $c$, we verify it is in $C(B_3)\cap \overline{C(B_2)}$ using Lemma 12 in $O(1)$ time, find its endpoints $l,r$ using Corollary 13, and add $(c,l,r)$ to $S_2$.