Suppose we have a stream $a_1,a_2,\dots ,a_n$$a_1,a_2,\dots ,a_n$a_(1),a_(2),dots,a_(n)a_{1}, a_{2}, \ldots, a_{n} of objects from an ordered universe. For simplicity we will assume that they are real numbers and more over that they are distinct (for simplicity). We would like to find the $k$$k$kk'th ranked element for some $1\le k\le n$$1\le k\le n$1 <= k <= n1 \leq k \leq n. In particular we may be interested in the median element. We will discuss exact and approximate versions of these problems. Another terminology for finding rank $k$$k$kk elements is quantiles. Given a number $\varphi$$\varphi$phi\phi where $0<\varphi \le 1$$0<\varphi \le 1$0 < phi <= 10<\phi \leq 1 we would like to return an element of rank $\varphi n$$\varphi n$phi n\phi n. This normalization allows us to talk about $ϵ$$ϵ$epsilon\epsilon-approximate quantiles for $ϵ\in [0,1)$$ϵ\in [0,1)$epsilon in[0,1)\epsilon \in[0,1). An $ϵ$$ϵ$epsilon\epsilon-approximate quantile is an element whose rank is at least $(\varphi -ϵ)n$$(\varphi -ϵ)n$(phi-epsilon)n(\phi-\epsilon) n and at most $(\varphi +ϵ)n$$(\varphi +ϵ)n$(phi+epsilon)n(\phi+\epsilon) n. In other words we are allowing an additive error of $ϵn$$ϵn$epsilon n\epsilon n. There is a large amount of literature on quantiles and quantile queries. In fact one of the earliest "streaming" papers is the one by Munro and Paterson [5] who described a $p$$p$pp-pass algorithm for selection using $\tilde{O}\left(n^{1/p}\right)$$\tilde{O}\left(n^{1/p}\right)$tilde(O)(n^(1//p))\tilde{O}\left(n^{1 / p}\right) space for any $p\ge 2$$p\ge 2$p >= 2p \geq 2. They also considered the "random-order" streaming setting which has become quite popular in recent years.

The material for these lectures is taken mainly from the excellent chapter/survey by Greenwald and Khanna [1]. We mainly refer to that chapter and describe here the outline of what we covered in lectures. We will omit proofs or give sketchy arguments and refer the reader to [1].

Suppose we want to be able to answer $ϵ$$ϵ$epsilon\epsilon-approximate quantile queries over an ordered set $S$$S$SS of $n$$n$nn elements. It is easy to see that we can simply pick elements of rank $i|S|/k$$i|S|/k$i|S|//ki|S| / k for $1\le i\le k\simeq 1/ϵ$$1\le i\le k\simeq 1/ϵ$1 <= i <= k≃1//epsilon1 \leq i \leq k \simeq 1 / \epsilon and store them as a summary and use the summary to answer any quantile query with an $ϵn$$ϵn$epsilon n\epsilon n additive error. However, to obtain these elements we first need to do selection which we can do in the offline setting if all we want is a concise summary. The question we will address is to find a summary in the streaming setting. In the sequel we will count space usage in terms of "words". Thus, the space usage for the preceding offline summary is $\mathrm{\Theta }(1/ϵ)$$\mathrm{\Theta }(1/ϵ)$Theta(1//epsilon)\Theta(1 / \epsilon).

We will see two algorithms. The first will create an $ϵ$$ϵ$epsilon\epsilon-approximate summary $[4]$$[4]$[4][4] with space $O(\frac{1}{ϵ}{\log }^2(ϵn))$$O\left(\frac{1}{ϵ}{\log }^2(ϵn)\right)$O((1)/(epsilon)log^(2)(epsilon n))O\left(\frac{1}{\epsilon} \log ^{2}(\epsilon n)\right) and is inspired by the ideas from the work of Munro and Paterson. Greenwald and Khanna [2] gave a different summary that uses $O(\frac{1}{ϵ}\log (ϵn))$$O\left(\frac{1}{ϵ}\log (ϵn)\right)$O((1)/(epsilon)log(epsilon n))O\left(\frac{1}{\epsilon} \log (\epsilon n)\right) space.

Following $[1]$$[1]$[1][1] we will think of a quantile summary $Q$$Q$QQ as storing a set of elements $\{q_1,q_2,\dots ,q_{\ell }\}$$\{q_1,q_2,\dots ,q_{\ell }\}${q_(1),q_(2),dots,q_(ℓ)}\{q_{1}, q_{2}, \ldots, q_{\ell}\} from $S$$S$SS along with an interval $[{\mathbf{r}\mathbf{m}\mathbf{i}\mathbf{n}}_Q(q_i),{\mathbf{r}\mathbf{m}\mathbf{a}\mathbf{x}}_Q(q_i)]$$[{\mathbf{r}\mathbf{m}\mathbf{i}\mathbf{n}}_Q(q_i),{\mathbf{r}\mathbf{m}\mathbf{a}\mathbf{x}}_Q(q_i)]$[rmin_(Q)(q_(i)),rmax_(Q)(q_(i))][\mathbf{rmin}_{Q}(q_{i}), \mathbf{rmax}_{Q}(q_{i})] for each $q_i;{\mathbf{r}\mathbf{m}\mathbf{i}\mathbf{n}}_Q(q_i)$$q_i;{\mathbf{r}\mathbf{m}\mathbf{i}\mathbf{n}}_Q(q_i)$q_(i);rmin_(Q)(q_(i))q_{i} ; \mathbf{rmin}_{Q}(q_{i}) is a lower bound on the rank of $q_i$$q_i$q_(i)q_{i} in $S$$S$SS and ${\mathbf{r}\mathbf{m}\mathbf{a}\mathbf{x}}_Q(q_i)$${\mathbf{r}\mathbf{m}\mathbf{a}\mathbf{x}}_Q(q_i)$rmax_(Q)(q_(i))\mathbf{rmax}_{Q}(q_{i}) is an upper bound on the rank of $q_i$$q_i$q_(i)q_{i} in $S$$S$SS. It is convenient to assume that $q_1<q_2<\dots <q_{\ell }$$q_1<q_2<\dots <q_{\ell }$q_(1) < q_(2) < dots < q_(ℓ)q_{1}<q_{2}<\ldots<q_{\ell} and moreover that $q_1$$q_1$q_(1)q_{1} is the minimum element in $S$$S$SS and that $q_{\ell }$$q_{\ell }$q_(ℓ)q_{\ell} is the maximum element in $S$$S$SS. For ease of notation we will simply use $Q$$Q$QQ to refer to the quantile summary and also the (ordered) set $\{q_1,q_2,\dots ,q_{\ell }\}$$\{q_1,q_2,\dots ,q_{\ell }\}${q_(1),q_(2),dots,q_(ℓ)}\{q_{1}, q_{2}, \ldots, q_{\ell}\}.

Our first question is to ask whether a quantile summary $Q$$Q$QQ can be used to give $ϵ$$ϵ$epsilon\epsilon-approximate quantile queries. The following is intuitive and is worthwhile proving for oneself.

Lemma 1 Suppose $Q$$Q$QQ is a quantile summary for $S$$S$SS such that for $1\le i<\ell ,{\mathbf{r}\mathbf{m}\mathbf{a}\mathbf{x}}_Q\left(q_{i+1}\right)-$$1\le i<\ell ,{\mathbf{r}\mathbf{m}\mathbf{a}\mathbf{x}}_Q\left(q_{i+1}\right)-$1 <= i < ℓ,rmax_(Q)(q_(i+1))-1 \leq i<\ell, \mathbf{rmax}_{Q}\left(q_{i+1}\right)- ${\mathbf{r}\mathbf{m}\mathbf{i}\mathbf{n}}_Q\left(q_i\right)\le 2ϵ|S|$${\mathbf{r}\mathbf{m}\mathbf{i}\mathbf{n}}_Q\left(q_i\right)\le 2ϵ|S|$rmin_(Q)(q_(i)) <= 2epsilon|S|\mathbf{rmin}_{Q}\left(q_{i}\right) \leq 2 \epsilon|S|. Then $Q$$Q$QQ can be used for $ϵ$$ϵ$epsilon\epsilon-approximate quantile queries over $S$$S$SS.

In the following, when we say that $Q$$Q$QQ is an $ϵ$$ϵ$epsilon\epsilon-approximate quantile summary we will implicitly be using the condition in the preceding lemma.

Given a quantile summary $Q^{\mathrm{\prime }}$$Q^{\mathrm{\prime }}$Q^(')Q^{\prime} for a multiset $S^{\mathrm{\prime }}$$S^{\mathrm{\prime }}$S^(')S^{\prime} and a quantile summary $Q^{\mathrm{\prime }\mathrm{\prime }}$$Q^{\mathrm{\prime }\mathrm{\prime }}$Q^('')Q^{\prime \prime} for a multiset $S^{\mathrm{\prime }\mathrm{\prime }}$$S^{\mathrm{\prime }\mathrm{\prime }}$S^('')S^{\prime \prime} we would like to combine $Q^{\mathrm{\prime }}$$Q^{\mathrm{\prime }}$Q^(')Q^{\prime} and $Q^{\mathrm{\prime }\mathrm{\prime }}$$Q^{\mathrm{\prime }\mathrm{\prime }}$Q^('')Q^{\prime \prime} into a quantile summary $Q$$Q$QQ for $S=S^{\mathrm{\prime }}\cup S^{\mathrm{\prime }\mathrm{\prime }}$$S=S^{\mathrm{\prime }}\cup S^{\mathrm{\prime }\mathrm{\prime }}$S=S^(')uuS^('')S=S^{\prime} \cup S^{\prime \prime}; by union here we view $S$$S$SS as a multiset. Of course we would like to keep the approximation of the resulting summary similar to those of $Q^{\mathrm{\prime }}$$Q^{\mathrm{\prime }}$Q^(')Q^{\prime} and $Q^{\mathrm{\prime }\mathrm{\prime }}$$Q^{\mathrm{\prime }\mathrm{\prime }}$Q^('')Q^{\prime \prime}. Here a lemma which shows that indeed we can easily combine.

Lemma 2 Let $Q^{\mathrm{\prime }}$$Q^{\mathrm{\prime }}$Q^(')Q^{\prime} be an ${ϵ}^{\mathrm{\prime }}$${ϵ}^{\mathrm{\prime }}$epsilon^(')\epsilon^{\prime}-approximate quantile summary for multiset $S^{\mathrm{\prime }}$$S^{\mathrm{\prime }}$S^(')S^{\prime} and $Q^{\mathrm{\prime }\mathrm{\prime }}$$Q^{\mathrm{\prime }\mathrm{\prime }}$Q^('')Q^{\prime \prime} be an ${ϵ}^{\mathrm{\prime }\mathrm{\prime }}$${ϵ}^{\mathrm{\prime }\mathrm{\prime }}$epsilon^('')\epsilon^{\prime \prime}-approximate quantile summary for multiset $S^{\mathrm{\prime }\mathrm{\prime }}$$S^{\mathrm{\prime }\mathrm{\prime }}$S^('')S^{\prime \prime}. Then $Q=Q^{\mathrm{\prime }}\cup Q^{\mathrm{\prime }\mathrm{\prime }}$$Q=Q^{\mathrm{\prime }}\cup Q^{\mathrm{\prime }\mathrm{\prime }}$Q=Q^(')uuQ^('')Q=Q^{\prime} \cup Q^{\prime \prime} yields an $ϵ$$ϵ$epsilon\epsilon-approximate quantile summary for $S=S^{\mathrm{\prime }}\cup S^{\mathrm{\prime }\mathrm{\prime }}$$S=S^{\mathrm{\prime }}\cup S^{\mathrm{\prime }\mathrm{\prime }}$S=S^(')uuS^('')S=S^{\prime} \cup S^{\prime \prime} where $ϵ\le \frac{{ϵ}^{\mathrm{\prime }}{n}^{\mathrm{\prime }}+{ϵ}^{\mathrm{\prime }\mathrm{\prime }}{n}^{\mathrm{\prime }\mathrm{\prime }}}{n^{\mathrm{\prime }}+n^{\mathrm{\prime }\mathrm{\prime }}}\le max\{{ϵ}^{\mathrm{\prime }}$$ϵ\le \frac{{ϵ}^{\mathrm{\prime }}{n}^{\mathrm{\prime }}+{ϵ}^{\mathrm{\prime }\mathrm{\prime }}{n}^{\mathrm{\prime }\mathrm{\prime }}}{n^{\mathrm{\prime }}+n^{\mathrm{\prime }\mathrm{\prime }}}\le max\left\{{ϵ}^{\mathrm{\prime }}\right.$epsilon <= (epsilon^(')n^(')+epsilon^('')n^(''))/(n^(')+n^('')) <= max{epsilon^('):}\epsilon \leq \frac{\epsilon^{\prime} n^{\prime}+\epsilon^{\prime \prime} n^{\prime \prime}}{n^{\prime}+n^{\prime \prime}} \leq \max \left\{\epsilon^{\prime}\right., ${ϵ}^{\mathrm{\prime }\mathrm{\prime }}\}$$\left.{ϵ}^{\mathrm{\prime }\mathrm{\prime }}\right\}${:epsilon^('')}\left.\epsilon^{\prime \prime}\right\} where $n^{\mathrm{\prime }}=\left|S^{\mathrm{\prime }}\right|$$n^{\mathrm{\prime }}=\left|S^{\mathrm{\prime }}\right|$n^(')=|S^(')|n^{\prime}=\left|S^{\prime}\right| and $n^{\mathrm{\prime }\mathrm{\prime }}=\left|S^{\mathrm{\prime }\mathrm{\prime }}\right|$$n^{\mathrm{\prime }\mathrm{\prime }}=\left|S^{\mathrm{\prime }\mathrm{\prime }}\right|$n^('')=|S^('')|n^{\prime \prime}=\left|S^{\prime \prime}\right|.

We will not prove the correctness but describe how the intervals are constructed for $Q$$Q$QQ from those for $Q^{\mathrm{\prime }}$$Q^{\mathrm{\prime }}$Q^(')Q^{\prime} and $Q^{\mathrm{\prime }\mathrm{\prime }}$$Q^{\mathrm{\prime }\mathrm{\prime }}$Q^('')Q^{\prime \prime}. Suppose $Q^{\mathrm{\prime }}=\{x_1,x_2,\dots ,x_a\}$$Q^{\mathrm{\prime }}=\{x_1,x_2,\dots ,x_a\}$Q^(')={x_(1),x_(2),dots,x_(a)}Q^{\prime}=\{x_{1}, x_{2}, \ldots, x_{a}\} and $Q^{\mathrm{\prime }\mathrm{\prime }}=\{y_1,y_2,\dots ,y_b\}$$Q^{\mathrm{\prime }\mathrm{\prime }}=\{y_1,y_2,\dots ,y_b\}$Q^('')={y_(1),y_(2),dots,y_(b)}Q^{\prime \prime}=\{y_{1}, y_{2}, \ldots, y_{b}\}. Let $Q=Q^{\mathrm{\prime }}\cup Q^{\mathrm{\prime }\mathrm{\prime }}=\{z_1,z_2,\dots ,z_{a+b}\}$$Q=Q^{\mathrm{\prime }}\cup Q^{\mathrm{\prime }\mathrm{\prime }}=\{z_1,z_2,\dots ,z_{a+b}\}$Q=Q^(')uuQ^('')={z_(1),z_(2),dots,z_(a+b)}Q=Q^{\prime} \cup Q^{\prime \prime}=\{z_{1}, z_{2}, \ldots, z_{a+b}\}. Consider some $z_i\in Q$$z_i\in Q$z_(i)in Qz_{i} \in Q and suppose $z_i=x_r$$z_i=x_r$z_(i)=x_(r)z_{i}=x_{r} for some $1\le r\le a$$1\le r\le a$1 <= r <= a1 \leq r \leq a. Let $y_s$$y_s$y_(s)y_{s} be the largest element of $Q^{\mathrm{\prime }\mathrm{\prime }}$$Q^{\mathrm{\prime }\mathrm{\prime }}$Q^('')Q^{\prime \prime} smaller than $x_r$$x_r$x_(r)x_{r} and $y_t$$y_t$y_(t)y_{t} be the smallest element of $Q^{\mathrm{\prime }\mathrm{\prime }}$$Q^{\mathrm{\prime }\mathrm{\prime }}$Q^('')Q^{\prime \prime} larger than $x_r$$x_r$x_(r)x_{r}. We will ignore the cases where one or both of $y_s,y_t$$y_s,y_t$y_(s),y_(t)y_{s}, y_{t} are not defined. We set

and

It is easy to justify the above as valid intervals. One can then prove that with these settings, for $1\le i<a+b$$1\le i<a+b$1 <= i < a+b1 \leq i<a+b the following holds:

We will refer to the above operation as $\mathrm{COMBINE}(Q^{\mathrm{\prime }},Q^{\mathrm{\prime }\mathrm{\prime }})$$\mathrm{COMBINE}(Q^{\mathrm{\prime }},Q^{\mathrm{\prime }\mathrm{\prime }})$COMBINE(Q^('),Q^(''))\operatorname{COMBINE}(Q^{\prime}, Q^{\prime \prime}). The following is easy to see.

Lemma 3 Let $Q_1,\dots ,Q_h$$Q_1,\dots ,Q_h$Q_(1),dots,Q_(h)Q_{1}, \ldots, Q_{h} be $ϵ$$ϵ$epsilon\epsilon-approximate quantile summaries for $S_1,S_2,\dots ,S_h$$S_1,S_2,\dots ,S_h$S_(1),S_(2),dots,S_(h)S_{1}, S_{2}, \ldots, S_{h} respectively. Then $Q_1,Q_2,\dots ,Q_h$$Q_1,Q_2,\dots ,Q_h$Q_(1),Q_(2),dots,Q_(h)Q_{1}, Q_{2}, \ldots, Q_{h} can be combined in any arbitrary order to obtain an $ϵ$$ϵ$epsilon\epsilon-approximate quantile summary $Q=Q_1\cup \dots \cup Q_h$$Q=Q_1\cup \dots \cup Q_h$Q=Q_(1)uu dots uuQ_(h)Q=Q_{1} \cup \ldots \cup Q_{h} for $S_1\cup \dots \cup S_h$$S_1\cup \dots \cup S_h$S_(1)uu dots uuS_(h)S_{1} \cup \ldots \cup S_{h}.

Next we discuss the $\mathrm{PRUNE}(Q,k)$$\mathrm{PRUNE}(Q,k)$PRUNE(Q,k)\operatorname{PRUNE}(Q, k) operation on a quantile summary $Q$$Q$QQ that reduces the size of $Q$$Q$QQ to $k+1$$k+1$k+1k+1 while losing a bit in the approximation quality.

Lemma 4 Let $Q^{\mathrm{\prime }}$$Q^{\mathrm{\prime }}$Q^(')Q^{\prime} be an $ϵ$$ϵ$epsilon\epsilon-approximate quantile summary for $S$$S$SS. Given an integer parameter $k$$k$kk there is a quantile summary $Q\subseteq Q^{\mathrm{\prime }}$$Q\subseteq Q^{\mathrm{\prime }}$Q subeQ^(')Q \subseteq Q^{\prime} for $S$$S$SS such that $|Q|\le k+1$$|Q|\le k+1$|Q| <= k+1|Q| \leq k+1 and it is $(ϵ+\frac{1}{2k})$$(ϵ+\frac{1}{2k})$(epsilon+(1)/(2k))(\epsilon+\frac{1}{2 k})-approximate.

We sketch the proof. We simply query $Q^{\mathrm{\prime }}$$Q^{\mathrm{\prime }}$Q^(')Q^{\prime} for ranks $1,|S|/k,2|S|/k,\dots ,|S|$$1,|S|/k,2|S|/k,\dots ,|S|$1,|S|//k,2|S|//k,dots,|S|1,|S| / k, 2|S| / k, \ldots,|S| and choose these elements to be in $Q$$Q$QQ. We retain their $\mathbf{r}\mathbf{m}\mathbf{i}\mathbf{n}$$\mathbf{r}\mathbf{m}\mathbf{i}\mathbf{n}$rmin\mathbf{rmin} and $\mathbf{r}\mathbf{m}\mathbf{a}\mathbf{x}$$\mathbf{r}\mathbf{m}\mathbf{a}\mathbf{x}$rmax\mathbf{rmax} values from $Q^{\mathrm{\prime }}$$Q^{\mathrm{\prime }}$Q^(')Q^{\prime}.

The idea is inspired by the Munro-Paterson algorithm and was abstracted in the paper by Manku et al. We will describe the idea in an offline fashion though it can be implemented in the streaming setting. We will use several quantile summaries with $k$$k$kk elements each for some parameter $k$$k$kk, say $\ell$$\ell$ℓ\ell of them. Each summary of size $k$$k$kk will be called a buffer. We will need to reuse these buffers as more elements in the stream arrive; buffers will combined and pruned, in other words "collapsed" into a single buffer of the same size $k$$k$kk. Pruning introduces error.

Assume $n/k$$n/k$n//kn / k is a power of 2 for simplicity. Consider a complete binary tree with $n/k$$n/k$n//kn / k leaves where each leaf corresponds to $k$$k$kk consecutive elements of the stream. Think of assigning a buffer of size $k$$k$kk to obtain a 0-error quantile summary for those $k$$k$kk elements; technically we need $k+1$$k+1$k+1k+1 elements but we will ignore this minor additive issue for sake of clarity of exposition. Now each internal node of the tree corresponds to a subset of the elements of the stream. Imagine assigning a buffer of size $k$$k$kk to each internal node to maintain an approximate quantile summary for the elements of the stream in the sub-tree. To obtain a summary at node $v$$v$vv we combine the summaries of its two children $v_1$$v_1$v_(1)v_{1} and $v_2$$v_2$v_(2)v_{2} and prune it back to size $k$$k$kk introducing and additional $1/(2k)$$1/(2k)$1//(2k)1 /(2 k) error in the approximation. The quantile summary at the root of size $k$$k$kk will be our final summary that we output for the stream.

Our first observation is that in fact we can implement the tree-based scheme with $\ell =O(h)$$\ell =O(h)$ℓ=O(h)\ell=O(h) buffers where $h$$h$hh is the height of the tree. Note that $h\simeq \log (n/k)$$h\simeq \log (n/k)$h≃log(n//k)h \simeq \log (n / k). The reason we only need $O(h)$$O(h)$O(h)O(h) buffers is that if need a new buffer for the next $k$$k$kk elements in the stream we can collapse two buffers corresponding to the children of an internal node - hence, at any time we need to maintain only one buffer per level of the tree (plus a temporary buffer to do the collapse operation).

Consider the quantile summary at the leaves. They have error 0 since we store all the elements in the buffer. However at each level the error increases by $1/(2k)$$1/(2k)$1//(2k)1 /(2 k). Hence the error of the summary at the root is $h/(2k)$$h/(2k)$h//(2k)h /(2 k). Thus, to obtain an $ϵ$$ϵ$epsilon\epsilon-approximate quantile summary we need $h/(2k)\le ϵ$$h/(2k)\le ϵ$h//(2k) <= epsilonh /(2 k) \leq \epsilon. And $h=\log (n/k)$$h=\log (n/k)$h=log(n//k)h=\log (n / k). One can see that for this to work out it suffices to choose $k>\frac{1}{2ϵ}\log (2ϵn)$$k>\frac{1}{2ϵ}\log (2ϵn)$k > (1)/(2epsilon)log(2epsilon n)k>\frac{1}{2 \epsilon} \log (2 \epsilon n).

The total space usage is $\mathrm{\Theta }(hk)$$\mathrm{\Theta }(hk)$Theta(hk)\Theta(h k) and $h=\log (n/k)$$h=\log (n/k)$h=log(n//k)h=\log (n / k) and thus the space usage is $O(\frac{1}{ϵ}{\log }^2(ϵn))$$O\left(\frac{1}{ϵ}{\log }^2(ϵn)\right)$O((1)/(epsilon)log^(2)(epsilon n))O\left(\frac{1}{\epsilon} \log ^{2}(\epsilon n)\right).

One can choose $d$$d$dd-ary trees instead of binary trees and some optimization can be done to improve the constants but the asymptotic dependence on $ϵ$$ϵ$epsilon\epsilon does not improve with this high-level scheme.

We now briefly describe the Greenwald-Khanna algorithm that obtains an improved space bound. The GK algorithm maintains a quantile summary as a collection of $s$$s$ss tuples $t_0,t_2,\dots ,t_{s-1}$$t_0,t_2,\dots ,t_{s-1}$t_(0),t_(2),dots,t_(s-1)t_{0}, t_{2}, \ldots, t_{s-1} where each tuple $t_i$$t_i$t_(i)t_{i} is a triple $(v_i,g_i,{\mathrm{\Delta }}_i)$$(v_i,g_i,{\mathrm{\Delta }}_i)$(v_(i),g_(i),Delta_(i))(v_{i}, g_{i}, \Delta_{i}) : (i) a value $v_i$$v_i$v_(i)v_{i} that is an element of the ordered set $S$$S$SS (ii) the value $g_i$$g_i$g_(i)g_{i} which is equal to ${\mathbf{r}\mathbf{m}\mathbf{i}\mathbf{n}}_{\mathrm{G}\mathrm{K}}(v_i)-{\mathbf{r}\mathbf{m}\mathbf{i}\mathbf{n}}_{\mathrm{G}\mathrm{K}}(v_{i-1})$${\mathbf{r}\mathbf{m}\mathbf{i}\mathbf{n}}_{\mathrm{G}\mathrm{K}}(v_i)-{\mathbf{r}\mathbf{m}\mathbf{i}\mathbf{n}}_{\mathrm{G}\mathrm{K}}(v_{i-1})$rmin_(GK)(v_(i))-rmin_(GK)(v_(i-1))\mathbf{rmin}_{\mathrm{GK}}(v_{i})-\mathbf{rmin}_{\mathrm{GK}}(v_{i-1}) (for $i=0,g_i=0$$i=0,g_i=0$i=0,g_(i)=0i=0, g_{i}=0 ) and (iii) the value ${\mathrm{\Delta }}_i$${\mathrm{\Delta }}_i$Delta_(i)\Delta_{i} which equals ${\mathbf{r}\mathbf{m}\mathbf{a}\mathbf{x}}_{\mathrm{G}\mathrm{K}}(v_i)-{\mathbf{r}\mathbf{m}\mathbf{i}\mathbf{n}}_{\mathrm{G}\mathrm{K}}(v_i)$${\mathbf{r}\mathbf{m}\mathbf{a}\mathbf{x}}_{\mathrm{G}\mathrm{K}}(v_i)-{\mathbf{r}\mathbf{m}\mathbf{i}\mathbf{n}}_{\mathrm{G}\mathrm{K}}(v_i)$rmax_(GK)(v_(i))-rmin_(GK)(v_(i))\mathbf{rmax}_{\mathrm{GK}}(v_{i})-\mathbf{rmin}_{\mathrm{GK}}(v_{i}). The elements $v_0,v_1,\dots ,v_{s-1}$$v_0,v_1,\dots ,v_{s-1}$v_(0),v_(1),dots,v_(s-1)v_{0}, v_{1}, \ldots, v_{s-1} are in ascending order and moreover $v_0$$v_0$v_(0)v_{0} will the minimum element in $S$$S$SS and $v_{s-1}$$v_{s-1}$v_(s-1)v_{s-1} is the maximum element in $S$$S$SS. Note that $n=\sum _{j=1}^{s-1}{g}_j$$n=\sum _{j=1}^{s-1} g_j$n=sum_(j=1)^(s-1)g_(j)n=\sum_{j=1}^{s-1} g_{j}. The summary also stores $n$$n$nn the number of elements seen so far. With this set up we note that ${\mathbf{r}\mathbf{m}\mathbf{i}\mathbf{n}}_{\mathrm{G}\mathrm{K}}(v_i)=\sum _{j\le i}{g}_j$${\mathbf{r}\mathbf{m}\mathbf{i}\mathbf{n}}_{\mathrm{G}\mathrm{K}}(v_i)=\sum _{j\le i} g_j$rmin_(GK)(v_(i))=sum_(j <= i)g_(j)\mathbf{r m i n}_{\mathrm{GK}}(v_{i})=\sum_{j \leq i} g_{j} and ${\mathbf{r}\mathbf{m}\mathbf{a}\mathbf{x}}_{\mathrm{G}\mathrm{K}}(v_i)={\mathrm{\Delta }}_i+\sum _{j\le i}{g}_j$${\mathbf{r}\mathbf{m}\mathbf{a}\mathbf{x}}_{\mathrm{G}\mathrm{K}}(v_i)={\mathrm{\Delta }}_i+\sum _{j\le i} g_j$rmax_(GK)(v_(i))=Delta_(i)+sum_(j <= i)g_(j)\mathbf{rmax}_{\mathrm{GK}}(v_{i})=\Delta_{i}+\sum_{j \leq i} g_{j}.

Lemma 5 Suppose $Q$$Q$QQ is a $GK$$GK$GKGK quantile summary for a set $|S|$$|S|$|S||S| such that $\underset{i}{max}(g_i+{\mathrm{\Delta }}_i)\le 2ϵ|S|$$\underset{i}{max} (g_i+{\mathrm{\Delta }}_i)\le 2ϵ|S|$max_(i)(g_(i)+Delta_(i)) <= 2epsilon|S|\max _{i}(g_{i}+\Delta_{i}) \leq 2 \epsilon|S| then it can be used to answer quantile queries with $ϵn$$ϵn$epsilon n\epsilon n additive error.

The query can be answered as follows. Given rank $r$$r$rr, find $i$$i$ii such that $r-{\mathbf{r}\mathbf{m}\mathbf{i}\mathbf{n}}_{\mathrm{G}\mathrm{K}}(v_i)\le ϵn$$r-{\mathbf{r}\mathbf{m}\mathbf{i}\mathbf{n}}_{\mathrm{G}\mathrm{K}}(v_i)\le ϵn$r-rmin_(GK)(v_(i)) <= epsilon nr-\mathbf{rmin}_{\mathrm{GK}}(v_{i}) \leq \epsilon n and ${\mathbf{r}\mathbf{m}\mathbf{a}\mathbf{x}}_{\mathrm{G}\mathrm{K}}(v_i)-r\le ϵn$${\mathbf{r}\mathbf{m}\mathbf{a}\mathbf{x}}_{\mathrm{G}\mathrm{K}}(v_i)-r\le ϵn$rmax_(GK)(v_(i))-r <= epsilon n\mathbf{rmax}_{\mathrm{GK}}(v_{i})-r \leq \epsilon n and output $v_i$$v_i$v_(i)v_{i}; here $n$$n$nn is the current size of $S$$S$SS.