arXiv:1603.05346v2 [] 5 Apr 2016

Optimal Quantile Approximation in Streams
Zohar Karnin
Yahoo Research

Kevin Lang
Yahoo Research

Edo Liberty
Yahoo Research

zkarnin@yahoo-inc.com

langk@yahoo-inc.com

edo@yahoo-inc.com

Abstract
This paper resolves one of the longest standing basic problems in the streaming computational model. Namely, optimal construction of quantile sketches. An ε approximate quantile
sketch receives a stream of items x1 , . . . , xn and allows one to approximate the rank of any query
up to additive error εn with probability at least 1 − δ. The rank of a query x is the number of
stream items such that xi ≤ x. The minimal sketch size required for this task is trivially at least
1/ε. Felber and Ostrovsky obtain a O((1/ε) log(1/ε)) space sketch for a fixed δ. To date, no
better upper or lower bounds were known even for randomly permuted streams or for approximating a specific quantile, e.g., the median. This paper obtains an O((1/ε) log log(1/δ)) space
sketch and a matching lower bound. This resolves the open problem and proves a qualitative gap
between randomized and deterministic quantile sketching. One of our contributions is a novel
representation and modification of the widely used merge-and-reduce construction. This subtle
modification allows for an analysis which is both tight and extremely simple. Similar techniques
should be useful for improving other sketching objectives and geometric coreset constructions.

1

Introduction

Given a set of items x1 , . . . , xn , the quantile of a value x is the fraction of items in the stream
such that xi ≤ x. It is convenient to define the rank of x, R(x), as the number of items such that
xi ≤ x. An additive error εn for R(x) is an ε approximation of its rank. The literature distinguishes
between several different definitions of this problem. In this manuscript we distinguish between the
single quantile approximation problem and the all quantiles approximation problem.
Definition 1. The single quantile approximation problem: Given x1 , . . . , xn in a streaming fashion
in arbitrary order, construct a data structure for computing R̃(x). By the end of the stream, receive
a single element x and compute R̃(x) such that |R̃(x) − R(x)| ≤ εn with probability 1 − δ.
There are variations of this problem in which, the algorithm is not given x (as a query) but rather
a rank r. It should be able to provide an element xi from the stream such that |R(xi ) − r| ≤ εn.
There are also variants that make the value r, or r/n known to the algorithm in advance. For
example, one could a priori choose to search for an approximate median.1 The solution we propose
solves all the above variants by solving a harder task called the all quantiles problem.
Definition 2. The all quantiles approximation problem: Given x1 , . . . , xn in a streaming fashion
in arbitrary order, construct a data structure for computing R̃(x). By the end of the stream, with
probability 1 − δ, for all values of x simultaneously it should hold that |R̃(x) − R(x)| ≤ εn.
1
We mention that there are easy reductions between the different variants that maintain the failure probability
and error up to a constant.

1

Observe that approximating a set of O(1/ε) single queries well suffices for solving the all quantiles approximation problem. Therefore, solving the single quantiles approximation problem with
failure probability at most εδ constitutes a valid solution for the all quantiles approximation problem simply by invoking the union bound.

1.1

Related Work

Two recent surveys [1][2] on this problem give ample motivation and explain the state of the art in
terms of algorithms and theory in a very accessible way.2 In what follows, we shortly review some
of the prior work that is most relevant in the context of this manuscript. For readability, space
complexities of randomized algorithms apply for a constant success probability unless otherwise
stated.
Manku, Rajagopalan and Lindsay [3] built on the work of Munro and Paterson [4] and gave a
randomized solution which uses at most O((1/ε) log2 (nε)) space. A simple deterministic version
of their algorithm achieves the same bounds. This was pointed out, for example, by [1]. We
refer to their algorithm as MRL. Greenwald and Khanna [5] created an intricate deterministic
algorithm that requires O((1/ε) log(nε)) space. This is the best known deterministic algorithm for
this problem. We refer to their algorithm as GK.
Allowing randomness enables sampling. A uniform sample of size n0 = O(log(1/ε)/ε2 ) from
the stream suffices to produce an all quantiles sketch. Feeding the sampled elements into a GK
sketch yields an O((1/ε) log(1/ε)) solution. However, to produce such samples, one must know
n (at least approximately) in advance. This observation was already made by Manku et al. [3].
Since n is not known in advance it is not a trivial task to combine sampling with GK sketches.
Recently, Felber and Ostrovsky [6] managed to do exactly that. They achieved space complexity of
O((1/ε) log(1/ε)) by using sampling and several GK sketches in conjunction in a non trivial way.
To the best of our knowledge, this is the best known space complexity result to date.
Mergeability: An important property of sketches is called mergability [7]. Informally, this property allows one to sketch different sections of the stream independently and then combine the
resulting sketches. The combined sketch should be as accurate as a single sketch one would have
computed had the entire stream been consumed by a single sketcher. This is formally stated in
Definition 3.
Definition 3. Let S denote a sketching algorithm mapping a stream N to a summary S(N ), and
denote by ε(S(N ), N ) the error associated with the summary S(N ) on the stream N . Let N1 , N2
denote two sequences of items, and let N = [N1 , N2 ] denote the sequence obtained by concatenating
N1 , N2 . A sketching algorithm S is mergeable if there exists a merge operation M such that
ε(M (S(N1 ), S(N2 )), N ) ≤ ε(S(N ), N )
This property is extremely important in practice since large datasets are often distributed across
many machines. Agarwal et al [7] conjecture that the GK sketch is not mergeable. They describe a
mergeable sketch of space complexity (1/ε) log3/2 (1/ε). It is worth noting that this results predates
that of [6].
2

Manuscript [2] was authored in 2007 as a book chapter. It does not contain recent results but is an excellent
survey nonetheless.

2

Model: Different sketching algorithms perform different kinds of operations on the elements in
the stream. The most restricted model is the comparison model. In this model, there is a strong
order imposed on the elements and the algorithm can only compare two items to decide which is
larger. This is the case, for example, for lexicographic ordering of strings. All the cited works above
operate in this model. Another model assumes the total size of the universe is bounded by |U |. An
O((1/ε) log(|U |)) space algorithm was suggested by [8] in that model. If the items are numbers, for
example, one could also compute averages or perform gradient descent like algorithms such as [9].
In machine learning, a quantile loss function refers to an asymmetric or weighted `1 loss. Predicting
the values of the items in the stream with the quantile loss converges to the correct quantiles. Such
methods however only apply to randomly shuffled streams.
Lower bounds: For any algorithm, there exists a (trivial) space lower bound of Ω(1/ε). Hung
and Ting [10] showed that any deterministic comparison based algorithm for the single quantile
approximation problem must store Ω((1/ε) log(1/ε)) items. Felber and Ostrovsky [6] suggest, as
an open problem, that the Ω((1/ε) log(1/ε)) lower bound could potentially hold for randomized
algorithms as well. Prior to this work, it was very reasonable to believe this conjecture is true. For
example, no o((1/ε) log(1/ε)) space algorithm was known even for randomly permuted streams.3

1.2

Main Contribution

We begin by re-explaining the work of [7] and the deterministic version of [3] from a slightly different
view point. The basic building block for these algorithms is a single compactor. A compactor can
store k items all with the same weight w. It can also compact its k elements into k/2 elements of
weight 2w as follows. First, the items are sorted. Then, either the even or the odd elements in
the sequence are chosen. The unchosen items are discarded. The weight of the chosen elements is
doubled (set to 2w). Consider a single query x. Its rank estimation before and after the compaction
defers by at most w regardless of k. This is illustrated in Figure 1.
This already gives a deterministic algorithm. Assume we use such a compactor. When it outputs
items, we feed them into another compactor and so on. Since each compactor halves the number
of items in the sequence, there could be at most H ≤ dlog(n/k)e compactors chained together. Let
h denote the height of a compactor where the last one created has height h = H and the first one
has height h = 1. Let wh = 2h−1 be the weight of items compactor h gets. Then, the number of
compact operations
PH it performs is at most mh = n/kwh . Summing up all the errors in the system
P
H
m
w
=
h=1 h h
h=1 n/k = Hn/k ≤ n log(n/k)/k. Since we have H compactors, the space usage
is kH ≤ k log(n/k). Setting k = O((1/ε) log(εn)) yields error of εn with space O((1/ε) log2 (εn)).
One conceptual contribution of Agarwal et al. [7] is to have each compactor delete the odd or
even items with equal probability. This has the benefit that the expected error is zero. It also lets
one use standard concentration results to bound the maximal error. This eliminates one log factor
from
adds a factor
p the worst case analysis. However, the dependence on the failure probability
p
of log(1/δ). In the all quantiles problem this translates into an additional log(1/ε) factor for
constant failure probability. Intuitively Agarwal et al. [7] also show that when n ≥ poly(1/ε) one
can sample
items from the stream
gives total space usage

 before feeding them to the sketch. This


p
p
of O (1/ε) log(1/ε) log(1/δ) for the single quantile problem and O (1/ε) log(1/ε) log(1/εδ)
for the all quantiles problem.
3

If the stream is presented in random order, obtaining an O((1/ε) log(1/ε)) solution is easy. Namely, save the first
O((1/ε) log(1/ε)) items and, from that point on, only count how many items fall between two consecutive samples.
Due to coupon collector, at least one sample will fall in each stretch of εn items which makes the solution trivially
correct.

3

R(x) = 2w

0!

1!

R(x) = 5w

3!

4!

5!

R(x) = 2w

0!

7!
R(x) = 6w

3!

5!

R(x) = 2w

R(x) = 4w

1!

4!
x

7!
x

Figure 1: An illustration of a single compactor with 6 items performing a single compaction operation. The rank of a query remains unchanged if its rank with in the compactor is even. If it is
odd, its rank is increased or decreased by w with equal probability by the compaction operation.
The first improvement we provide to the algorithms above is to use different compactor capacities in different heights, denoted by kh . We show that kh can, for example, decrease exponentially
kh ≈ kH (2/3)H−h . That is, compactors in lower levels in the hierarchy can operate with significantly less capacity. Surprisingly enough, this turns out to not effect the asymptotic statistical
behavior of the error at all. Moreover, the space complexity is clearly improved.
The capacity of any functioning compactor must be at least 2. This could contribute O(H) =
O(log(n/k)) to the space complexity. To remove this dependence, we notice that a sequence of H 00
00
compactors with capacity 2 essentially perform sampling. Out of every 2H elements they select
00
one at random and output that element with weight 2H . This is clearly very efficiently computable
and does not truly require memory complexity of O(H 00 ) butPrather of O(1). The total capacity of
H−h ≤ 3k. This yields
all compactors whose capacity is more than 2 is bounded by H
h=H 00 +1 k(2/3)
p
a total space complexity
of O(k). Setting k = O((1/ε) log(1/δ)) gives anp
algorithm with space
p
complexity O((1/ε) log(1/δ)) for the single quantile problem and O((1/ε) log(1/ε)) for the all
quantiles problem, which constitutes our first result. Interestingly, our algorithm can be thought
of a smooth interpolation between carful compaction of heavy items and efficient sampling for light
items. We believe this idea would be potentially useful in other geometric coreset construction
problems.
The next improvement comes from special handling of the top log log(1/δ) compactors. Intuitively, the number of compaction operations (and therefore random bits) in those levels is so small
that one could expect the worst case behavior. For worst case analysis a fixed kh is preferred to
diminishing values of kh . Therefore, we suggest to set kh = k when h ≥ H − O(log log(1/δ)) and
kh ≈ k(2/3)H−h otherwise. By analyzing the worst case error of the top log log(1/δ) compactors
separately from the bottom H −log log(1/δ) we improve our analysis to O((1/ε) log2 log(1/δ)). This
sketch is fully mergeable. Interestingly, the worst case analysis of the top log log(1/δ) compactors
is identical to the analysis of the MRL sketch above.
This last observation leads us to our third and final improvement. If one replaces the top
log log(1/δ) compactors with a GK sketch, the space complexity can be shown to reduce to
O((1/ε) log log(1/δ)). However, this prevents the sketch from being mergeable because the GK
sketch is not known to have this property.
Another way to view this algorithm is as a concatenation of three sketches. The first, receiving
4

the stream of elements is a sampler that simulates all the compactors of capacity 2. Its output is
fed into a sketch composed of a sequence of compactors of increasing sizes, as described above. We
refer to such a sketch as a KLL sketch. This sketch outputs O((1/ε) poly log(1/δ)) items that are
fed into an instance of GK. This idea is illustrated in Figure 2.
log(n) compactors !

1/"2 items of !
weight ! n"2

O(log(1/")) compactors !

n items of !
weight 1!

Sampler!

O(log log(1/ ))
compactors of
equal capacity!

(1/") poly log(1/ )
items of weight !
n"/ poly log(1/ )

1/"2 items of !
weight ! n"2

n items of !
weight 1!

Sampler!

GK sketch!

Figure 2: Sampling, varying capacity compactors, equal capacity compactors and GK sketches
achieve different efficiencies at different stream lengths. The set of capacitated compactors used by
KLL creates a smooth transition between sampling and GK sketching. The top figure corresponds
to the first construction explained in Section 2. The second from the top is explained in Section 3.
The two bottom figures correspond to our main contributions and are explained in Sections 4
and 4.1 respectively.

2

Algorithm and Analysis

As mentioned above, our sketching algorithm (KLL) includes a hierarchy of compactors with varying
capacities. Consider a run of the algorithm that terminates with H different compactors. The
compactors are indexed by their hight h ∈ 1, . . . , H. The weight of items at hight h is wh = 2h−1 .
Denote by kh the smallest number of items that the compactor at height h contains during a
compact operation. For brevity, denote k = kH . For reasons that will become clear later assume
that kh ≥ kcH−h for c ∈ (0.5, 1).
5

MRL [3]
GK [5]
ACHPWY [7]
FO [6]
c
δ = e−(1/ε)
KLL
[This paper]
KLL
[This paper]

Single quantile

All quantiles

Randomized

(1/ε) log2 (εn)

(1/ε) log2 (εn)

No

Yes

No

No

Yes

Yes

(1/ε) log(εn)
p
(1/ε) log(1/ε) log(1/δ)

(1/ε) log(εn)
p
(1/ε) log(1/ε) log(1/εδ)

Mergeable

(1/ε) log(1/ε)

(1/ε) log(1/ε)

Yes

No

(1/ε) log2 log(1/δ)

(1/ε) log2 log(1/δε)

Yes

Yes

(1/ε) log log(1/δ)

(1/ε) log log(1/δε)

Yes

No

Table 1: The table describes the space complexity of several streaming quantiles algorithms in bigO notation. The randomized algorithms are required to succeed with constant probability. They
all work in the comparison model and for arbitrarily ordered streams. The non-mergeability of
some of these algorithms is due to the fact that they use GK, which is not known to be mergeable,
as a subroutine.
Since the top compactor was created, we know that the second compactor from the top compacted its elements at least once. Therefore n ≥ kH−1 wH−1 = kH−1 2H−2 which gives
H ≤ log(n/kH−1 ) + 2 ≤ log(n/ck) + 2 .
Using the above we can bound the number of compact operations mh at height h. Every compact
procedure call is performed on at least kh items and the items have a weight of wh = 2h−1 .
Therefore,
n
2n
mh ≤
≤ H (2/c)H−h ≤ (2/c)H−h−1 .
kh wh
k2
To analyze the total error produced by the sketch, we first consider the error generated in each
individual level. Define by R(k, h) the rank of x among the following weighted set of items. The
items yielded by the compactor at height h and all the items stored in the compactors of heights
h0 ≤ h at end of the stream. For convenience R(x, 0) = R(x) is the exact rank of x in the input
stream. Define err(x, h) = R(x, h) − R(x, h − 1) to be the total change in the approximated rank
of x due to level h.
Note that each compaction operation in level h either leaves the rank of x unchanged or adds
wh or subtracts wh with equal probability. To be more explicit, if x has an even rank among the
item inside the compactor, the total mass to the left of it (its rank) is unchanged by the compaction
operation. If its rank inside the compactor is odd however and the odd items are chosen, this mass
increases by wh . If its rank inside the compactor
is odd and the even items are chosen, its mass
Pmh
decreases by wh . Therefore, err(x, h) = i=1 wh Xi,h where E[Xi,h ] = 0 and |Xi,h | ≤ 1. The final
discrepancy between the real rank of x and its approximation R̃(x) = R(x, H) is
R(x, H) − R(x, 0) =

H
X

R(x, h) − R(x, h − 1) =

h=1

H
X
h=1

err(x, h) =

mh
H X
X

wh Xi,h .

h=1 i=1

Lemma 1 (Hoeffding). Let X1 , . . . , Xm be independent random variables, each with an expected
value of zero, taking values in the range [−wi , wi ]. Then for any t > 0 we have
" m
#


X
t2
Pr
Xi > t ≤ 2 exp − Pm
2 i=1 wi2
i=1
6

with exp being the natural exponent function.
We now apply Hoeffding’s inequality to bound the probability that the bottom H 0 ≤ H compactors contribute more than εn to the total error. The reason for considering only the bottom
levels and not all the levels will become apparent in Section 3.
" H0 m
#
!
h
2 n2
XX



ε
(1)
Pr R x, H 0 − R(x, 0) > εn = Pr
wh Xi,h > εn ≤ 2 exp − PH 0 Pm
h
2 h=1 i=1
wh2
h=1 i=1
A straight forward computation shows that
0

mh
H X
X

0

wh2

=

h=1 i=1

H
X

0

mh wh2

h=1

h=1
H 0 −1

=
0

H
X
0
≤
(c/2)H −h−1 22h−1

(2/c)
4

H0

0
0
X
(2/c)H −1 (2c)H
c
0
h
(2c) ≤
≤
22H
4
2c − 1
8(2c − 1)

h=1

0

Substituting 22H = 22H /22(H−H ) and recalling that H ≤ log(n/ck) + 2 we get that
0

mh
H X
X
h=1 i=1

wh2 ≤

n2 /k 2
1
0)
2
2(H−H
2c (2c − 1) 2

(2)

Substituting Equation 2 into Equation 1 and setting C = c2 (2c − 1) we get the following convenient
form




0
(3)
Pr |R(x, H 0 ) − R(x)| ≥ εn ≤ 2 exp −Cε2 k 2 22(H−H )
Theorem 1. There exists a streaming algorithm that computes an ε approximation
for the rank of
p
a single item with probability 1 − δ whose space complexity is O((1/ε) log(1/δ) + log(εn)). This
algorithm also produces mergeable summaries.


Proof. Let kh = kcH−h + 1. Note that kh changes throughout the run off the algorithm. Nevertheless, H can only increase and so kh is monotonically decreasing with the length of the stream.
This matches the requirement that kh ≥ kcH−h where H is the final number of compactors. Notice
that kh is at least 2.
Setting H 0 = H in Equation 3 and requiring failure probability at most δ we conclude that it
p
PH
suffices to set k = (C/ε) log(2/δ). The space complexity of the algorithm is O
h=1 kh .
H
X
h=1

kh ≤

H
X

(kcH−h + 2) ≤ k/(1 − c) + 2H = O(k + log(n/k))

h=1

Setting δ = Ω(ε) suffices to union bound over the failure probabilities of O(1/ε) different quantiles.
p
This provides a mergeable sketching algorithm for the all quantiles problem of space O((1/ε) log(1/ε)+
log(εn)).
The KLL sketch provides a mergeable summary. In a merge operation, same height compactors
are concatenated together. Then, each level that contains more than kh elements is compacted.
The value of kh is based on the new maximal height H which is derived from the combined lengths
of the two streams. In either of the two merged sketches, each compaction at level h involved at
least kh items which means the proof above still holds.

7

Note that this result already improves on the best known prior art in the parameter setting where
n = exp(O(1/ε)).
Theorem 2. There exists a streaming algorithm that computes an
 ε approximation
 for the rank of
p
a single item with probability 1 − δ whose space complexity is O (1/ε) log(1/δ) .
Proof. The KLL sketch maintains a total of H = log(εn) sketches. Note, however, that only
O(log(k)) compactors have capacity greater than 2. More accurately the bottom H 00 = H −
dlog(k)/ log(1/c)e all have capacity exactly 2. Each of those receives two items at a time, performs
a random match between them, and sends the winner of the match to the compactor of the next
level. Hence, the compactor of level H 00 simply selects one item uniformly at random from every
00
00
2H elements in the stream and passes that item with weight 2H to the compactor at hight H 00 + 1.
This is easily simulated using O(1) space which replaces the bottom H 00 compactors and reduces
the space complexity of the algorithm.
There is, however, a drawback in replacing the bottom H 00 compactors with a simple sampler.
When merging two sketches, it is not clear how to merge the samplers in a correct way. The next
section explains how to do exactly that.

3

Sampling and Keeping Mergeablity

In the new sketch we have, in addition to the compactors, a new object we call a sampler. The
sampler supports an update method that introduces an item of weight w to the sketch. When
observing items in a stream the weight is always set to 1. However, when merging two sketches
we require supporting an update of arbitrary weights. At any time the sampler has an associated
height h. It outputs items of weight 2h as inputs to the compactor of level h + 1. This associated
height will increase over time to eventually being roughly H − log(1/ε). Apart for sampler of height
h, the sketch maintains compactors at heights greater than h.
The sampler keeps a single item in storage along with a weight of at most 2h − 1. When merging
two sketches, the sketch with the sampler of smaller height will feed its item with its appropriate
weight to the sampler of the other sketch. Also, all compactors with height ≤ h in the ‘smaller’
sketch will feed the items in their buffers to the sampler of the ‘larger sketch’.
The update operation is performed as follows. Denote by v the weight of the internal item
stored in the sampler and by w the weight of the newly introduced item. If v + w ≤ 2h , the sampler
replaces its stored item with the new one with probability w/(v + w) as in Reservoir Sampling. If
v + w = 2h the sampler outputs the stored item and sets the internal weight w to 0. If however
v + w > 2h (notice this can only happen if w > 1) the sampler discards the heavier item, and keeps
the lighter item with a weight of min{w, v}. With probability max{w, v}/2h it also outputs the
heavier item with weight 2h .
It is easy to verify that the above described sketching scheme corresponds to the following
offline operations. The sampler outputs items by performing the action sample; it takes as input a
sequence of items W items such that 2h−1 < W ≤ 2h .With probability W/2h it outputs one of the
observed items chosen at random. With probability 1 − W/2h it outputs nothing. Before analyzing
the error associated with a sample operation we mention that, if no merges are performed, it suffices
to restrict the value of W to be exactly 2h . However, in order to account for merges we must let
W obtain values in the range W ∈ (2h−1 , 2h ].
Lemma 2. Let R(x, h, i) be the rank of x after sample operation i of the sampler of height h, where
the rank is computed based on the stream elements that did not undergo a sample operation, and the
8

weighted items outputted by the sample operations 1 through i. Let R(x, h, i)−R(x, h, i−1) = 2h Yh,i .
Then E[Yh,i ] = 0 and |Yh,i | ≤ 1.
Proof. Let r be the exact rank of x among the input items before the sampling operation. Denote by
W the sum of weights of the input items. After the sampling, those input items are replaced with a
single element. The rank of x after the sampling is 2h with probability W
· r and 0 otherwise. The
2h W
first term is the probability of outputting anything. The second is of selecting an element smaller
than x. Therefore, the expected value of the rank of x after the sample operation is 2h W
· r = r,
2h W
hence the expected value of the difference mentioned in the claim is 0. Clearly, the maximal value
of this difference is bounded by 2h .
Let mh be total number of times a sample operation can be performed at height h. Since the
sampler at that height takes items with a total minimum weight of W > 2h−1 and there are a total
of n items (with overall weight n)
n
mh ≤ h−1 .
2
It follows that the expression of the error accounted for samplers of heights up to4 H 00 can be
expressed as
mh
mh
H 00 X
H 00 X
X
X
errH 00 =
[R(x, h, i) − R(x, h, i − 1)] =
2h Yi,h
h=1 i=1

h=1 i=1

with Yi,h being independent, E[Yi,h ] = 0 and |Yi,h | ≤ 1. We compute the sum of weights appearing
in Hoeffding’s inequality (Lemma 1) in order to apply it.
00

mh
H X
X
h=1 i=1

00

2h

2

≤

H
X

00

n2h+1 ≤ 4n2H =

h=1

4n2H
16n2
≤
2H−H 00
ck2H−H 00

Hence,


00
Pr [errH 00 > εn] ≤ 2 exp −cε2 k2H−H /32 .

(4)

The following is immediate from Equations 3 and 4.
Theorem 3. Assume we apply a KLL sketch that uses H levels of compactors, with capacity
kh ≥ kcH−h . Also, assume that an arbitrary subset of the stream is fed into samplers of heights
1 through H 00 , while the output of these samplers is fed to appropriate compactors. Then for any
H 0 > H 00 it holds that




00
0
Pr [errH 0 > 2εn] < 2 exp −cε2 k2H−H /32 + 2 exp −Cε2 k 2 22(H−H )
Here, errH 0 denotes the error of the stream outputted by the compactors of level H 0 , and C =
c2 (2c − 1).
p
By taking H 0 = H, H 00 = H − O(log(k)), and k = (1/ε) log(1/δ) we obtain the following
corollary.
Corollary 1. There exists a streaming algorithm that computes an ε approximation
for the rank of
p
a single item with probability 1 − δ whose space complexity is O((1/ε) log(1/δ)). This algorithm
also produced mergeable summaries.
4

Notice that unlike compactors, there is no hierarchy of samplers. However, due to the fact that the height of the
sampler grows with time, the sample operations may be performed on different heights. The only guarantee is that
any item appears in at most one sample operation and that the height of the sampler is always at most H 00 .

9

4

Reducing the Failure Probability

In this section we take full advantage of Theorem 3 to obtain a streaming algorithm with asymptotically better space complexity. Notice that the lion share of the contribution to the error is due to
the top compactors. For those, however, Hoeffding’s bound is not tight. Let s = O(log log(1/δ)) be
a small number of top layers. For the bottom H −s layers we use Theorem 3, applied on H 0 = H −s
and corresponding H 00 , to bound their error. For the top s we simply use a deterministic bound.
Theorem 4. There exists a streaming algorithm that computes an ε approximation for the rank of
a single item with probability 1 − δ whose space complexity is O((1/ε) log2 log(1/δ)). This algorithm
also produces mergeable summaries.
Proof. Using Theorem 3 we see that the bottom compactors of height at most H 0 = H − s and the
sampler, when set to be of height at most H 00 =p
H − 2s − log2 (k), contribute at most εn to the
s
0
error with probability 1 − δ at long as εk2 ≥ c log(2/δ) for sufficiently small constant c0 . For
the top s compactors, we set their capacities to kh = k. That P
is, we do not let their
PHcapacity drop
m
w
=
exponentially. Those levels contribute to the error at most H
h=H 0 +1 h h
h=H 0 +1 n/kh =
sn/k. Requiring that this contribution is at most εn as well we obtain the relation s ≤ kε. Setting
s = O(log log(1/δ)) and k = O( 1ε log log(1/δ)) satisfies both conditions. The space complexity of
this algorithm is dominated by maintaining the top s levels which is O(ks) = O((1/ε) log2 log(1/δ)).
Interestingly, the analysis of the top s levels is identical to the equal capacity compactors used
in the MRL sketch. In the next section we show that one could replace the top s levels with a
different algorithm and reduce the dependence on δ even further.

4.1

Gaining Space Optimality; Potentially Losing Mergeability

The most space efficient version of our algorithm, with respect to the failure probability, operates
as follows. For δ being the target error probability we set
l
m
 p
s = log2 c0 log(2/δ)/(kε) = O(log log(1/δ))
as in the section above but set k = O(1/ε). At any time point we keep 2 different copies of the GK
sketch, tuned for a relative error of ε. They are correspondingly associated with the compactors
of heights h1 < h2 which are the two largest height values that are multiples of s. The GK sketch
associated with height h receives as input the outputs of the compactor of layer h − 1. For h = 0
the GK sketch associated with it receives as input the stream elements. When a new GK sketch is
built due to a new compactor being formed the bottom one is discarded.
Theorem 5. There exists a streaming algorithm that computes an ε approximation for the rank of
a single item with probability 1 − δ whose space complexity is O((1/ε) log log(1/δ)).
Proof. Notice that the height of h1 is at least H − 2s. It follows that the total number of items
that is ever fed into a single GK sketch at most n1 = k22s . Applying Theorem 3 again, on
H 0 = H − s, and H 00 = H − 2s − log2 (k), the error w.r.t. to the output of the compactor feeding
elements into the GK sketch matching h1 is at most O(εn), with k = O(1/ε). Therefore, the sum
of errors is still O(εn). The memory required by the GK sketch with respect to its input is at most
O((1/ε) log(εn1 )) = O ((1/ε)s) = O ((1/ε) log log(1/δ)), which dominates the memory of our sketch
with k = O(1/ε). The claim follows.
10

We note that the GK sketch is not known to be fully mergeable and so that property of the
sketch is lost by this construction. That being said, we point out that the GK sketch is one-way
mergeable. One-way mergeability is a weaker form of mergeability that informally states that the
following setting can work: The data is partitioned among several machine, each creates a summary
of its own data, and a single process merges all of the summaries into a single one. For example,
stated in terms of Definition 3, when the error ε(S(N ), N ) is linear in the size of the sketch N ,
i.e., ε(S(N ), N ) = εS |N |, a merge operation resulting in an error of εS |N1 | + 2εS |N2 | rather than
εS |N1 | + εS |N2 | is one-way mergeable, while it is not (fully) mergeable. It was pointed out by [2, 7]
that any sketch for the all quantiles approximation problem is one-way mergeable.

5

Tightness of Our Result

In [10] a lower bound is given for deterministic algorithms. A more precise statement of their result,
implicitly shown in the proof of their Theorem 2, is as follows
Lemma 3 (Implicit in [10], Theorem 2). Let AD be deterministic comparison based algorithm
solving single quantile ε approximate for all streams of length at most C(1/ε)2 log(1/ε)2 for some
sufficiently large universal constant C. Then AD must store at least c(1/ε) log(1/ε) elements from
the stream for some sufficiently small constant c.
Below we obtain a lower bound matching our result completely for the case of single quantile
problem and almost completely for the case of ε approximation of all quantiles.
Theorem 6. Let AR be a randomized comparison based algorithm solving the ε approximate single
quantile problem with probability at least 1 − δ. Then AR must store at least Ω ((1/ε) log log(1/δ))
elements from the stream.
Proof. Assume by contradiction that there exists a randomized algorithm AR that succeeds in
computing a single quantile approximation up to error ε with probability 1 − δ while storing
o ((1/ε) log log(1/δ)) elements from the stream. Let n be the length of the stream and δ = 1/2n!.
With probability 1/2 the randomized algorithm succeeds simultaneously for all n! possible inputs. Let r denote a sequence of random bits used by AR in one of these instances. It is
now possible to construct a deterministic algorithm AD (r) which is identical to AR but with
r hardcoded into it. Note that AD (r) deterministically succeeds for streams of length n. Let
n = C(1/ε)2 log(1/ε)2 for the same C as in Lemma 3. We obtain that AD (r) succeeds on all
streams of length C(1/ε)2 log(1/ε)2 while storing o((1/ε) log(1/ε)) elements from the stream. This
contradicts Lemma 3 above.

6

Discussion

The lower bound above perfectly matched the single quantile approximation result we achieve.
For the all quantiles problem, using the union bound over a set of O(1/ε) quantiles shows that
O((1/ε) log log(1/ε)) elements suffice. This leaves a potential gap of log log(1/ε) for that problem.

Acknowledgments
The authors want to thank Sanjeev Khanna, Rafail Ostrovsky, Jeff Phillips, Graham Cormode,
Andrew McGregor and Piotr Indyk for very helpful discussions and pointers.
11

References
[1] Lu Wang, Ge Luo, Ke Yi, and Graham Cormode. Quantiles over data streams: An experimental study. In Proceedings of the 2013 ACM SIGMOD International Conference on Management
of Data, SIGMOD ’13, pages 737–748, New York, NY, USA, 2013. ACM.
[2] Michael B. Greenwald and Sanjeev Khanna. Quantiles and equidepth histograms over streams.
In J. Gehrke M. Garofalakis and R. Rastogi, editors, In Data Stream Management: Processing
High-Speed Data Streams. Springer, 2016.
[3] Gurmeet Singh Manku, Sridhar Rajagopalan, and Bruce G. Lindsay. Random sampling techniques for space efficient online computation of order statistics of large datasets. SIGMOD
Rec., 28(2):251–262, June 1999.
[4] J.I. Munro and M.S. Paterson. Selection and sorting with limited storage. Theoretical Computer Science, 12(3):315 – 323, 1980.
[5] Michael Greenwald and Sanjeev Khanna. Space-efficient online computation of quantile summaries. In Proceedings of the 2001 ACM SIGMOD International Conference on Management
of Data, SIGMOD ’01, pages 58–66, New York, NY, USA, 2001. ACM.
[6] David Felber and Rafail Ostrovsky.
A randomized online quantile summary in
O((1/ε) log(1/ε)) words. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2015, August 24-26, 2015, Princeton,
NJ, USA, pages 775–785, 2015.
[7] Pankaj K. Agarwal, Graham Cormode, Zengfeng Huang, Jeff Phillips, Zhewei Wei, and Ke Yi.
Mergeable summaries. In Proceedings of the 31st Symposium on Principles of Database Systems, PODS ’12, pages 23–34, New York, NY, USA, 2012. ACM.
[8] Nisheeth Shrivastava, Chiranjeeb Buragohain, Divyakant Agrawal, and Subhash Suri. Medians
and beyond: New aggregation techniques for sensor networks. In Proceedings of the 2Nd
International Conference on Embedded Networked Sensor Systems, SenSys ’04, pages 239–249,
New York, NY, USA, 2004. ACM.
[9] Andrej Brodnik, Alejandro Lopez-Ortiz, Venkatesh Raman, and Alfredo Viola. Space-Efficient
Data Structures, Streams, and Algorithms: Papers in Honor of J. Ian Munro, on the Occasion
of His 66th Birthday, volume 8066. Springer, 2013.
[10] Regant YS Hung and Hingfung F Ting. A (1/ε) log(1/ε) space lower bound for finding εapproximate quantiles in a data stream. In Frontiers in Algorithmics, pages 89–100. Springer,
2010.

12

