Q-Digest

Problem

Let $d \in \mathbb{N}^+$ be a positive integer and $f = (0, \ldots, 0) \in \mathbb{R}^d$ be an all-zero vector. There is a sequence $S$ of updates, each of which consists of a pair $(x, w) \in [d] \times \mathbb{R}^+$, increasing $f[x]$ by $w$.

Model Description

1. $f \leftarrow (0, \ldots, 0) \in \mathbb{R}^d$;
2. For $(x, w) \in S$ do
3. $\qquad$ $f[x] \leftarrow f[x] + w$;

After witnessing the stream $S$, we call $f$ the frequency vector. We are interested in answering the following query.

Rank Query
Input： $x \in [d]$
Returen: $r[x] \leftarrow \sum_{i = 1}^{x - 1} f[i]$.

We formally define the problem of approximate rank estimation.

Problem. Let $\epsilon$ be an error parameter. Design an algorithm, such that for a rank query with a given element $x \in [d]$, the summary will return an approximate rank $\hat r [x]$, such that

$$r[x] − \epsilon \cdot W \le \hat r [x] \le r[x] + \epsilon \cdot W.$$

$Q$-Digest

The naive solution maintain the vector $f \in \mathbb{R}^d$ explicitly. Assuming that each entry of $f$ can always be stored in one word, the space usage of the is $O(d)$.

Theorem. There exists an algorithm, $Q$-digest, that has space usage of $O( \frac{1}{\epsilon} \log d)$ words, insertion time $O(\log d)$ and query time of $O(\log d)$.

We first study a prototype which requires $O(d)$ words.

Prototype

The algorithm maintains an array of size $d$ to keep all values of $f$. Further, it construct a binary tree on the array, such that

1. Each node $v$ keeps the sum of frequencies of leaves in its subtree, denote as $s[v]$.

By definition, if $v$ is a leaf node, then $s[v]$ equals the frequency of the node. For each node $v$, denote $L[v]$ and $R[v]$ its left and right children respectively.

The figure below is an example with $d = 8$ and $f = (0, 1, 1, 0, 2, 1, 0, 1)$.

Insertion

To construct the tree, we can initialize a tree built on the domain $[d]$ with all counters $s[v]$ equal to $0$. Then on each pair of update $(x, w) \in S$, we invoke the following algorithm.

Update: $(x, w)$

1. $v \leftarrow$ root;
2. while $v$ is not a leaf do
3. $\qquad$ $s[v] \leftarrow s[v] + w$;
4. $\qquad$ if $x$ is in the left tree of $v$ then
5. $\qquad$ $\qquad$ $v \leftarrow L[v]$
6. $\qquad$ else
7. $\qquad$ $\qquad$ $v \leftarrow R[v]$
8. $s[v] \leftarrow s[v] + w$;

The update takes time $O(\log d)$.

Query

The query algorithm is also very simple. Given an input $x$, the algorithm walks down the path from the root to the leaf that contains $x$. The rank of $x$ equals the sum of of $s[v]$ for the $v$ such that

1. it is a left child of some node on the path;
2. it is not on the path.

Rank Query
Input： $x \in [d]$

1. $v \leftarrow root$;
2. $\hat r \leftarrow 0$;
3. while $v$ is not a leaf node do
4. $\qquad$ if $x$ is in left subtree of $v$ then
5. $\qquad$ $\qquad$ $v \leftarrow L[v]$
6. $\qquad$else
7. $\qquad$ $\qquad$ $\hat r \leftarrow \hat r + s[ L[v] ]$;
8. $\qquad$ $\qquad$ $v \leftarrow R[v]$
9. return $\hat r$

The query algorithm has time complexity $O(\log d)$.

$Q$-Digest

In this section, we show how to reduce the space usage to $O(\frac{1}{\epsilon} \log d)$.

In the previous section, when the algorithm perform a rank query for $x \in [d]$, it walks down a path $(v_1, \ldots, v_{\log d} )$, where $v_1$ is the root of the tree, and $v_{\log d}$ is the leaf node that contains $x$.

There are $\log d$ nodes in the path in total. If each node introduces an error of $O(\epsilon W / \log d)$ to the estimation of $r[x]$, then the final estimation has error bounded by $O(\epsilon W)$.

This motivates to associate each node $v$ in the tree with an error counter $c[v]$, which is interpreted as the maximum error it can introduce to the rank estimation to a given element $x$. It is initialized with $0$ and is guaranteed to be bounded by some threshold $C$ (except the leaf node). The threshold $C$ is updated along with the insertion of elements into the tree. The algorithm maintains the invariant that

Under this invariant, the estimation of $r[x]$ is always bounded by $\epsilon \cdot W$.

Insertion

The insertion algorithm is very simple. When an update $(x, w)$ arrives, the algorithm walks through the path from the root to the leaf that contains $x$. For each internal node $v$ in the path, the amount of additional error it can make is $C - c[v]$. If this amount is greater than $w$, then we just increase $c[v]$ by $w$, and stops the algorithm. Intuitively, we insert $x$ into this node. On the other hand, if $C - c[v]$ is less than $w$, then we can still partial insert $x$ into $v$, detailed by the pseudo-code below. Doing so increase the rank estimation error only for the element greater than $x$, but not for the elements less than or equal to $x$. Finally, if the invariant of $C$ does not hold, we need to update $C$ and the tree.

Update: $(x, w)$

1. $W \leftarrow W + w$;
2. $v \leftarrow$ root;
3. while $w > 0$ and $v$ is not a leaf do
4. $\qquad$ $s[v] \leftarrow s[v] + w$;
5. $\qquad$ $t \leftarrow \min\{ C - c[v], w\}$;
6. $\qquad$ $c[v] \leftarrow c[v] + t$;
7. $\qquad$ $w \leftarrow w - t$;
8. $\qquad$ if $x$ is in the left tree of $v$ then
9. $\qquad$ $\qquad$ $v \leftarrow L[v]$
10. $\qquad$ else
11. $\qquad$ $\qquad$ $v \leftarrow R[v]$
12. $s[v] \leftarrow s[v] + w$;
13. $c[v] \leftarrow c[v] + w$;
14. if $C \le \frac{\epsilon \cdot W}{2 \log d}$ then
15. $\qquad$ $C \leftarrow \frac{\epsilon \cdot W}{\log d}$;
16. $\qquad$ Compress(root, 0) // update the tree

Query

The query algorithm is the same as the one in the previous section, except that if algorithm encounters a node $v$ with $c[v] = 0$, then the algorithm can terminate earlier.

Maintenance

Finally, we discuss how to update the tree in a top-down approach. For a node $v$, we try to increase $c[v]$ to $C$, by borrowing weights from the its descendent. There are two possible cases. First, if $s[v] \le C$, then we can set $c[v] = C$ and delete all descendants of $v$. Otherwise, setting $c[v] = C$ incurs a "debt" of $d \doteq C - c[v]$ that $v$'s descendants need to pay. We assign as much debt as possible to the left child.

Compress $(v,d)$

1. if $c[v] = 0$ then return;
2. if v is a leaf node then
3. $\qquad$ $c[v] \leftarrow c[v] − d$
4. else
5. $\qquad$ if $s[v] > C + d$ then
6. $\qquad$ $\qquad$ $d \leftarrow d + C - c[v]$;
7. $\qquad$ $\qquad$ $c[v] \leftarrow C$;
8. $\qquad$ $\qquad$ $u \leftarrow L[v]$;
9. $\qquad$ $\qquad$ Compress $(L[v], \min(d , s[u] ) )$;
10. $\qquad$ $\qquad$ Compress $(R[v], \max(d − s[u] , 0 ) )$;
11. $\qquad$ else
12. $\qquad$ $\qquad$ $c[v] \leftarrow s[v] − d$;
13. $\qquad$ $\qquad$ Set weight of all descendants of $v$ to $0$;

By induction, we can show that $d \le s[v]$.

Space Usage

A node is called "saturated" if $c[v] = C$. By the invariant of $C$, there are at most $W / C = O((1 / \epsilon ) \log d)$ "saturated" nodes. By the algorithm, each node $v$ in the tree with nonzero $c[v]$, either "saturated", or has a "saturated" parent. However, each "saturated" can have at most two children. Therefore, the total number of nodes with nonzero $c[v]$ is bounded by $O((1 / \epsilon ) \log d)$.

Reference

[1] G. Cormode and K. Yi, Small Summaries for Big Data, 1st ed. Cambridge University Press, 2020.