Two-dimensional arrays

Gagie et al.^[12] proposed a data structure that supports range ${\displaystyle \tau }$-majority queries on an ${\displaystyle m\times n}$ array ${\displaystyle A}$. For each query ${\displaystyle \operatorname {Q} =(\operatorname {R} ,\tau )}$ in this data structure a threshold ${\displaystyle 0<\tau <1}$ and a rectangular range ${\displaystyle \operatorname {R} }$ are specified, and the set of all elements that have relative frequencies (inside that rectangular range) greater than or equal to ${\displaystyle \tau }$ are returned as the output. This data structure supports dynamic thresholds (specified at query time) and a pre-processing threshold ${\displaystyle \alpha }$ based on which it is constructed. During the pre-processing, a set of vertical and horizontal intervals are built on the ${\displaystyle m\times n}$ array. Together, a vertical and a horizontal interval form a block. Each block is part of a superblock nine times bigger than itself (three times the size of the block's horizontal interval and three times the size of its vertical one). For each block a set of candidates (with ${\displaystyle {\frac {9}{\alpha }}}$ elements at most) is stored which consists of elements that have relative frequencies at least ${\displaystyle {\frac {\alpha }{9}}}$ (the pre-processing threshold as mentioned above) in its respective superblock. These elements are stored in non-increasing order according to their frequencies and it is easy to see that, any element that has a relative frequency at least ${\displaystyle \alpha }$ in a block must appear its set of candidates. Each ${\displaystyle \tau }$-majority query is first answered by finding the query block, or the biggest block that is contained in the provided query rectangle in ${\displaystyle O(1)}$ time. For the obtained query block, the first ${\displaystyle {\frac {9}{\tau }}}$ candidates are returned (without being verified) in ${\displaystyle O(1/\tau )}$ time, so this process might return some false positives. Many other data structures (as discussed below) have proposed methods for verifying each candidate in constant time and thus maintaining the ${\displaystyle O(1/\tau )}$ query time while returning no false positives. The cases in which the query block is smaller than ${\displaystyle 1/\alpha }$ are handled by storing ${\displaystyle \log \left({\frac {1}{\alpha }}\right)}$ different instances of this data structure of the following form:

${\displaystyle \beta =2^{-i},\;\;i\in \left\{1,\dots ,\log \left({\frac {1}{\alpha }}\right)\right\}}$

where ${\displaystyle \beta }$ is the pre-processing threshold of the ${\displaystyle i}$-th instance. Thus, for query blocks smaller than ${\displaystyle 1/\alpha }$ the ${\displaystyle \lceil \log(1/\tau )\rceil }$-th instance is queried. As mentioned above, this data structure has query time ${\displaystyle O(1/\tau )}$ and requires ${\displaystyle O\left(mn(H+1)\log ^{2}\left({\frac {1}{\alpha }}\right)\right)}$ bits of space by storing a Huffman-encoded copy of it (note the ${\displaystyle \log({\frac {1}{\alpha }})}$ factor and also see Huffman coding).

One-dimensional arrays

Chan et al.^[13] proposed a data structure that given a one-dimensional array${\displaystyle A}$, a subrange ${\displaystyle R}$ of ${\displaystyle A}$ (specified at query time) and a threshold ${\displaystyle \tau }$ (specified at query time), is able to return the list of all ${\displaystyle \tau }$-majorities in ${\displaystyle O(1/\tau )}$ time requiring ${\displaystyle O(n\log n)}$ words of space. To answer such queries, Chan et al.^[13] begin by noting that there exists a data structure capable of returning the top-k most frequent items in a range in ${\displaystyle O(k)}$ time requiring ${\displaystyle O(n)}$ words of space. For a one-dimensional array ${\displaystyle A[0,..,n-1]}$, let a one-sided top-k range query to be of form ${\displaystyle A[0..i]{\text{ for }}0\leq i\leq n-1}$. For a maximal range of ranges ${\displaystyle A[0..i]{\text{ through }}A[0..j]}$ in which the frequency of a distinct element ${\displaystyle e}$ in ${\displaystyle A}$ remains unchanged (and equal to ${\displaystyle f}$), a horizontal line segment is constructed. The ${\displaystyle x}$-interval of this line segment corresponds to ${\displaystyle [i,j]}$ and it has a ${\displaystyle y}$-value equal to ${\displaystyle f}$. Since adding each element to ${\displaystyle A}$ changes the frequency of exactly one distinct element, the aforementioned process creates ${\displaystyle O(n)}$ line segments. Moreover, for a vertical line ${\displaystyle x=i}$ all horizonal line segments intersecting it are sorted according to their frequencies. Note that, each horizontal line segment with ${\displaystyle x}$-interval ${\displaystyle [\ell ,r]}$ corresponds to exactly one distinct element ${\displaystyle e}$ in ${\displaystyle A}$, such that ${\displaystyle A[\ell ]=e}$. A top-k query can then be answered by shooting a vertical ray ${\displaystyle x=i}$ and reporting the first ${\displaystyle k}$ horizontal line segments that intersect it (remember from above that these line segments are already sorted according to their frequencies) in ${\displaystyle O(k)}$ time.

Chan et al.^[13] first construct a range tree in which each branching node stores one copy of the data structure described above for one-sided range top-k queries and each leaf represents an element from ${\displaystyle A}$. The top-k data structure at each node is constructed based on the values existing in the subtrees of that node and is meant to answer one-sided range top-k queries. Please note that for a one-dimensional array ${\displaystyle A}$, a range tree can be constructed by dividing ${\displaystyle A}$ into two halves and recursing on both halves; therefore, each node of the resulting range tree represents a range. It can also be seen that this range tree requires ${\displaystyle O(n\log n)}$ words of space, because there are ${\displaystyle O(\log n)}$ levels and each level ${\displaystyle \ell }$ has ${\displaystyle 2^{\ell }}$ nodes. Moreover, since at each level ${\displaystyle \ell }$ of a range tree all nodes have a total of ${\displaystyle n}$ elements of ${\displaystyle A}$ at their subtrees and since there are ${\displaystyle O(\log n)}$ levels, the space complexity of this range tree is ${\displaystyle O(n\log n)}$.

Using this structure, a range ${\displaystyle \tau }$-majority query ${\displaystyle A[i..j]}$ on ${\displaystyle A[0..n-1]}$ with ${\displaystyle 0\leq i\leq j\leq n}$ is answered as follows. First, the lowest common ancestor (LCA) of leaf nodes ${\displaystyle i}$ and ${\displaystyle j}$ is found in constant time. Note that there exists a data structure requiring ${\displaystyle O(n)}$ bits of space that is capable of answering the LCA queries in ${\displaystyle O(1)}$ time.^[14] Let ${\displaystyle z}$ denote the LCA of ${\displaystyle i}$ and ${\displaystyle j}$, using ${\displaystyle z}$ and according to the decomposability of range ${\displaystyle \tau }$-majority queries (as described above and in ^[11]), the two-sided range query ${\displaystyle A[i..j]}$ can be converted into two one-sided range top-k queries (from ${\displaystyle z}$ to ${\displaystyle i}$ and ${\displaystyle j}$). These two one-sided range top-k queries return the top-(${\displaystyle 1/\tau }$) most frequent elements in each of their respective ranges in ${\displaystyle O(1/\tau )}$ time. These frequent elements make up the set of candidates for ${\displaystyle \tau }$-majorities in ${\displaystyle A[i..j]}$ in which there are ${\displaystyle O(1/\tau )}$ candidates some of which might be false positives. Each candidate is then assessed in constant time using a linear-space data structure (as described in Lemma 3 in ^[15]) that is able to determine in ${\displaystyle O(1)}$ time whether or not a given subrange of an array ${\displaystyle A}$ contains at least ${\displaystyle q}$ instances of a particular element ${\displaystyle e}$.

Tree paths

Gagie et al.^[16] proposed a data structure which supports queries such that, given two nodes ${\displaystyle u}$ and ${\displaystyle v}$ in a tree, are able to report the list of elements that have a greater relative frequency than ${\displaystyle \tau }$ on the path from ${\displaystyle u}$ to ${\displaystyle v}$. More formally, let ${\displaystyle T}$ be a labelled tree in which each node has a label from an alphabet of size ${\displaystyle \sigma }$. Let ${\displaystyle label(u)\in [1,\dots ,\sigma ]}$ denote the label of node ${\displaystyle u}$ in ${\displaystyle T}$. Let ${\displaystyle P_{uv}}$ denote the unique path from ${\displaystyle u}$ to ${\displaystyle v}$ in ${\displaystyle T}$ in which middle nodes are listed in the order they are visited. Given ${\displaystyle T}$, and a fixed (specified during pre-processing) threshold ${\displaystyle 0<\tau <1}$, a query ${\displaystyle Q(u,v)}$ must return the set of all labels that appear more than ${\displaystyle \tau |P_{uv}|}$ times in ${\displaystyle P_{uv}}$.

To construct this data structure, first ${\displaystyle {O}(\tau n)}$ nodes are marked. This can be done by marking any node that has distance at least ${\displaystyle \lceil 1/\tau \rceil }$ from the bottom of the three (height) and whose depth is divisible by ${\displaystyle \lceil 1/\tau \rceil }$. After doing this, it can be observed that the distance between each node and its nearest marked ancestor is less than ${\displaystyle 2\lceil 1/\tau \rceil }$. For a marked node ${\displaystyle x}$, ${\displaystyle \log(depth(x))}$ different sequences (paths towards the root) ${\displaystyle P_{i}(x)}$ are stored,

${\displaystyle P_{i}(x)=\left\langle \operatorname {label} (x),\operatorname {par} (x),\operatorname {par} ^{2}(x),\ldots ,\operatorname {par} ^{2^{i}}(x)\right\rangle }$

for ${\displaystyle 0\leq i\leq \log(depth(x))}$ where ${\displaystyle \operatorname {par} (x)}$ returns the label of the direct parent of node ${\displaystyle x}$. Put another way, for each marked node, the set of all paths with a power of two length (plus one for the node itself) towards the root is stored. Moreover, for each ${\displaystyle P_{i}(x)}$, the set of all majority candidates ${\displaystyle C_{i}(x)}$ are stored. More specifically, ${\displaystyle C_{i}(x)}$ contains the set of all ${\displaystyle (\tau /2)}$-majorities in ${\displaystyle P_{i}(x)}$ or labels that appear more than ${\displaystyle (\tau /2).(2^{i}+1)}$ times in ${\displaystyle P_{i}(x)}$. It is easy to see that the set of candidates ${\displaystyle C_{i}(x)}$ can have at most ${\displaystyle 2/\tau }$ distinct labels for each ${\displaystyle i}$. Gagie et al.^[16] then note that the set of all ${\displaystyle \tau }$-majorities in the path from any marked node ${\displaystyle x}$ to one of its ancestors ${\displaystyle z}$ is included in some ${\displaystyle C_{i}(x)}$ (Lemma 2 in ^[16]) since the length of ${\displaystyle P_{i}(x)}$ is equal to ${\displaystyle (2^{i}+1)}$ thus there exists a ${\displaystyle P_{i}(x)}$ for ${\displaystyle 0\leq i\leq \log(depth(x))}$ whose length is between ${\displaystyle d_{xz}{\text{ and }}2d_{xz}}$ where ${\displaystyle d_{xz}}$ is the distance between x and z. The existence of such ${\displaystyle P_{i}(x)}$ implies that a ${\displaystyle \tau }$-majority in the path from ${\displaystyle x}$ to ${\displaystyle z}$ must be a ${\displaystyle (\tau /2)}$-majority in ${\displaystyle P_{i}(x)}$, and thus must appear in ${\displaystyle C_{i}(x)}$. It is easy to see that this data structure require ${\displaystyle O(n\log n)}$ words of space, because as mentioned above in the construction phase ${\displaystyle O(\tau n)}$ nodes are marked and for each marked node some candidate sets are stored. By definition, for each marked node ${\displaystyle O(\log n)}$ of such sets are stores, each of which contains ${\displaystyle O(1/\tau )}$ candidates. Therefore, this data structure requires ${\displaystyle O(\log n\times (1/\tau )\times \tau n)=O(n\log n)}$ words of space. Please note that each node ${\displaystyle x}$ also stores ${\displaystyle count(x)}$ which is equal to the number of instances of ${\displaystyle label(x)}$ on the path from ${\displaystyle x}$ to the root of ${\displaystyle T}$, this does not increase the space complexity since it only adds a constant number of words per node.

Each query between two nodes ${\displaystyle u}$ and ${\displaystyle v}$ can be answered by using the decomposability property (as explained above) of range ${\displaystyle \tau }$-majority queries and by breaking the query path between ${\displaystyle u}$ and ${\displaystyle v}$ into four subpaths. Let ${\displaystyle z}$ be the lowest common ancestor of ${\displaystyle u}$ and ${\displaystyle v}$, with ${\displaystyle x}$ and ${\displaystyle y}$ being the nearest marked ancestors of ${\displaystyle u}$ and ${\displaystyle v}$ respectively. The path from ${\displaystyle u}$ to ${\displaystyle v}$ is decomposed into the paths from ${\displaystyle u}$ and ${\displaystyle v}$ to ${\displaystyle x}$ and ${\displaystyle y}$ respectively (the size of these paths are smaller than ${\displaystyle 2\lceil 1/\tau \rceil }$ by definition, all of which are considered as candidates), and the paths from ${\displaystyle x}$ and ${\displaystyle y}$ to ${\displaystyle z}$ (by finding the suitable ${\displaystyle C_{i}(x)}$ as explained above and considering all of its labels as candidates). Please note that, boundary nodes have to be handled accordingly so that all of these subpaths are disjoint and from all of them a set of ${\displaystyle O(1/\tau )}$ candidates is derived. Each of these candidates is then verified using a combination of the ${\displaystyle labelanc(x,\ell )}$ query which returns the lowest ancestor of node ${\displaystyle x}$ that has label ${\displaystyle \ell }$ and the ${\displaystyle count(x)}$ fields of each node. On a ${\displaystyle w}$-bit RAM and an alphabet of size ${\displaystyle \sigma }$, the ${\displaystyle labelanc(x,\ell )}$ query can be answered in ${\displaystyle O\left(\log \log _{w}\sigma \right)}$ time whilst having linear space requirements.^[17] Therefore, verifying each of the ${\displaystyle O(1/\tau )}$ candidates in ${\displaystyle O\left(\log \log _{w}\sigma \right)}$ time results in ${\displaystyle O\left((1/\tau )\log \log _{w}\sigma \right)}$ total query time for returning the set of all ${\displaystyle \tau }$-majorities on the path from ${\displaystyle u}$ to ${\displaystyle v}$.