A High-Performance Algorithm for Identifying Frequent Items in
Data Streams
Daniel Anderson∗

Pryce Bevin†

Kevin Lang‡

Edo Liberty§

Lee Rhodes¶

arXiv:1705.07001v2 [cs.DS] 22 May 2017

Justin Thalerk

Abstract
Estimating frequencies of items over data streams is a common building block in streaming data measurement
and analysis. Misra and Gries introduced their seminal algorithm for the problem in 1982, and the problem has since
been revisited many times due its practicality and applicability. We describe a highly optimized version of Misra and
Gries’ algorithm that is suitable for deployment in industrial settings. Our code is made public via an open source
library called DataSketches that is already used by several companies and production systems.
Our algorithm improves on two theoretical and practical aspects of prior work. First, it handles weighted updates
in amortized constant time, a common requirement in practice. Second, it uses a simple and fast method for merging summaries that asymptotically improves on prior work even for unweighted streams. We describe experiments
confirming that our algorithms are more efficient than prior proposals.

1

Introduction

Identifying frequent items (also known as heavy hitters) and answering point queries (i.e., queries of the form “approximately how many times did item i appear in the stream?) are two of the most basic computational tasks performed on data streams. Due to their practical importance, streaming algorithms for these tasks have been studied
intensely [2–4,6,7,9,13–17]. It may therefore seem as though streaming frequency approximation is well-understood,
with little room for further insight or improvement. However, when we set about implementing an algorithm suitable
for industrial use on web-scale data, we found that existing algorithms had significant shortcomings. In this work, we
describe these shortcomings and present an optimized algorithm that addresses them.

1.1

Our Contributions

Our algorithm is similar to the popular Misra-Gries (MG) [17] and Space Saving (SS) [16] algorithms. However,
it differs from them in several simple yet important ways. Specifically, our algorithm handles weighted updates in a
highly efficient manner. It runs in amortized constant time per stream update, and employs optimized data structures to
minimize its memory footprint while maximizing throughput. We also give a simple and efficient method for merging
summaries produced by our algorithm, or more generally, any counter-based algorithm (cf. Section 1.3 for a definition
of this class of algorithms). Our merging procedure significantly improves on prior work even for unweighted streams.
We present experimental results validating the superiority of our algorithms over existing solutions.
Our experiments also clarify conventional wisdom regarding the best way to implement frequent items algorithms
in practice. Prior literature strongly suggested that the best algorithm in practice is a min-heap based implementation
∗ Georgetown
† Georgetown

University.
University.

‡ Yahoo.
§ Amazon.

Research performed while at Yahoo Research.

¶ Yahoo.
k Georgetown

University. Parts of this work were performed while the author was at Yahoo Research.

1

of SS (we denote this implementation of SS by MHE, cf. Section 1.3.5). Indeed, experimental work of Cormode
and Hadjieleftheriou [7] that focused exclusively on the setting of unweighted streams identified SS as state of the
art. They showed that a linked-list based implementation of SS (denoted in [7] as SSL) is noticeably faster than the
min-heap based implementation, but also significantly more space intensive. Moreover, SSL does not naturally extend
to weighted updates, while MHE does. Based on these findings, subsequent work (e.g., [18]) in the weighted setting
used MHE as the implementation of choice. We overturn this conventional wisdom: our implementations do not use
a min-heap, yet are significantly faster and more space efficient than MHE.

1.2

Problem Statement and Motivation

Given a data stream σ of length n over a universe [m] P
= {1, . . . , m}, where each stream update is of the form (ij , ∆j )
for some ij ∈ [m] and ∆j > 0 is a weight, let fi = j : ij =i ∆j denote the (weighted) frequency of i in the stream
P
and let N = j ∆j denote the weighted stream length. The goal of an algorithm for answering point queries is the
following. In a single pass over the stream, the algorithm must compute a small summary (sometimes also called a
sketch)1 of the stream such that, for any item i ∈ [m], it is possible to efficiently derive an estimate fˆi such that |fˆi −fi |
is small.
Ideally, the algorithm should also be able to identify (φ, ε)-heavy hitters (in the `1 -norm). That is, given a userspecified threshold φ, the algorithm should be able to identify all items i with fi ≥ φ · N , possibly also returning a
small number of “false positive” items whose frequency is slightly below the specified threshold φN .
We note that algorithms for answering point queries and identifying heavy hitters are often used in a black-box
fashion as subroutines in streaming algorithms solving more complicated problems. These include estimating the
empirical entropy of a data stream [5], and identifying hierarchical heavy hitters [18], both of which have important
applications in network data analysis and anomaly detection [8, 10, 22–24]. Our optimized algorithms for answering point queries and identifying heavy hitters can be directly substituted into these more complicated algorithms.
While we leave this task to future work, we expect that our optimizations would yield similar speed and memory
improvements in these settings.
The Importance of Weighted Updates The majority of the literature on streaming approximate frequency analysis
considers the case of unweighted updates, where ∆j = 1 for all j. However, there are many applications in which the
ability to efficiently handle weighted updates is critical. For example:
• It is often useful to track the total amount of data users send over a network, or the total time that users spend
using a mobile app or watching online video.
• In spam detection, it is useful to track the total number of recipients of emails from a given address, and many
emails have an enormous number of recipients.
• Weighted updates arise naturally whenever items from the data universe are associated with importance factors.
For example, in information-retrieval and text mining, term frequency–inverse document frequency (tf-idf for
short) is a standard statistic that assigns a value to each word in a document that is part of a larger corpus. The
value assigned to a word increases with the number of times a word appears in the document, but decreases with
the frequency of the word in the corpus, in order to account for the fact that some words appear more frequently
in general.
• We will also see (cf. Section 3.2) that the ability to efficiently handle weighted updates enables extremely
efficient merging of summaries – significantly faster than merging procedures proposed in prior work.
Unlike algorithms tailored to unweighted updates, algorithms capable of handling weighted updates typically apply to
real-valued weights. This will be the case for the algorithms we give in this work.
There are a number of simple ways to modify algorithms for the unweighted setting to handle the weighted setting.
However, as we describe in Section 1.3.4, all of the modifications that (to our knowledge) have been proposed in prior
work have significant shortcomings.
1 Some

works use the term sketch to refer only to a specific class of summaries known as linear sketches.

2

1.3

Overview of Prior Work

In a comprehensive paper and survey, Cormode and Hadjieleftheriou [7] provide a detailed comparison of proposed
algorithms for finding heavy hitters and answering point queries in the case of unit weight updates. They classified algorithms into three classes: counter-based algorithms, quantile algorithms, and (linear) sketches. They found
that counter-based algorithms perform significantly better in terms of space, speed, and accuracy than quantile and
sketching algorithms, a finding that we confirmed in our own initial experiments. Hence, we focus on counter-based
algorithms for the remainder of this work.
Note. The main advantage of sketches over counter-based algorithms is the ability to handle streams with deletions
(i.e., streams in the strict turnstile model, in which the ∆j ’s may be negative, yet for each i the final frequency fi of
i is non-negative). Specifically,
P in the strict turnstile model, sketch algorithms can return frequency estimates with
error proportional to N = j ∆j . While deletions are not encountered in the applications we target in this work
(cf. Section 1.2), we note here P
that any counter-based algorithm
P can easily be used to handle deletions at the cost
of having error proportional to j |∆j | rather than to N = j ∆j . To achieve this, simply apply one instance of
a counter-based algorithm to all the positive-weight updates, and a second instance to (the absolute value of) of all
negative weight updates, and define the estimate for fi to be the difference of the estimates for i returned by the two
instances. By the triangle inequality, the error of any estimated frequency
is at most the sum of the errors
P
P of the two
sketches. This approach will be suitable in applications in which j |∆j | is not much larger than N = j ∆j .
1.3.1

Counter-Based Algorithms

A counter-based algorithm stores k counters, where k is a parameter of the algorithm that controls both the space
usage and the error (larger k corresponds to more space and less error). Each counter stores an approximate count for
some item of the data universe; the various counter-based algorithms differ in how they assign counters to items and
how they determine the approximate counts.
Cormode and Hadjieleftheriou [7] found that two counter-based algorithms are state of the art: Misra-Gries (MG)
[17] and Space Saving (SS) [16]. They found that the estimates returned by SS tend to be more accurate than those
returned by MG – we discuss the reasons for the improved accuracy of SS relative to MG in Section 2.3.1. However,
subsequent work by Agarwal et al. [1] observed that these two algorithms are actually isomorphic, in the following
sense. The estimates returned by the SS algorithm with k + 1 counters can be derived from the summary computed by
the MG algorithm with k counters. That is, the summaries computed by both SS and MG contain essentially the same
information about the stream, but the algorithms differ in how they use this information to determine a “best estimate”
for any point query.
Our algorithm can be naturally viewed as an extension and modification of MG. Hence, we now describe MG in
detail.
1.3.2

Description of the Misra-Gries Algorithm For Unit Weight Updates

Every time the algorithm processes a stream update (i, +1), the MG algorithm looks to see if i is assigned a counter,
and if so it increments the counter. If not, and an unassigned counter exists, the algorithm assigns the counter to i and
sets the approximate count to 1. If no unassigned counter exists, the algorithm decrements all counters by 1, and marks
all counters set to 0 as unassigned. When asked to provide an estimate fˆi for the frequency of item fi , the algorithm
returns 0 if i is not assigned a counter, and returns the value of the counter assigned to i otherwise.
See Algorithm 1 for pseudocode. The following standard lemma bounds the error of any estimate returned by the
MG algorithm [17], and we provide the proof for completeness.
Lemma 1. The MG algorithm with k counters is guaranteed to return, for each i ∈ [n], and estimate fˆi satisfying
0 ≤ fi − fˆi ≤ N/(k + 1).
Proof. It is obvious from the description of the algorithm that 0 ≤ fi − fˆi for all i. To prove that fi − fˆi ≤ N/k for all
i, observe that fi − fˆi is at most the total number of decrement operations over the course of the algorithm, and there
can be at most N/k decrement operations. Indeed, if there are d decrement operations, then since each decrement
3

Algorithm 1 Misra-Gries Algorithm for Unit Weight Updates
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:

Algorithm: Misra-Gries(k):
T ← ∅ // T is set of items assigned a counter
Function Update(i, +1):
if i ∈ T :
c(i) ← c(i) + 1
else if |T | < k:
T = T ∪ {i}
c(i) ← 1
else:
DecrementCounters()
Function DecrementCounters():
for all j ∈ T :
c(j) = c(j) − 1
if c(j) = 0:
T = T \ {j}
Function Estimate(i):
if i ∈ T
return c(i)
else
return 0

operation affects all k counters, the sum of the counter values at the end of the algorithm is exactly N − d · (k + 1).
Since no counter value is ever negative, it holds that N − d · (k + 1) ≥ 0, and hence d ≤ N/(k + 1).
Using a similar proof, Berinde et al. [2] show that the MG algorithm also satisfies the following guarantee. This
guarantee, referred to by Berinde et al. as a tail guarantee, is much stronger than Lemma 1 for streams with a
very skewed frequency distribution (i.e., with a relatively small number of frequent items constituting the bulk of the
stream).
Lemma 2 (Berinde et al. [2]). Let N res(j) denote the sum of the frequencies of all but the top j most frequent items.
For any j < k, the MG algorithm with k counters is guaranteed to return, for each i ∈ [n], and estimate fˆi satisfying
0 ≤ fi − fˆi ≤ N res(j) /(k + 1 − j).
Efficiently Implementing Misra-Gries for Unit Weight Updates. A natural way to implement the MG algorithm is
to maintain a hash table that stores all assigned counters. The key for a counter is the item it is assigned to, and the
value is the count. Whenever a stream update (i, +1) arrives, the algorithm looks up key i in the hash table, and if it
is present, it increments the corresponding value (i.e., count). If not, the algorithm checks to see if the hash table is
storing k key-value pairs. If not, the key-value pair (i, 1) is inserted into the hash table. If so, the algorithm iterates
over all key-value pairs in the hash table, decrementing each value and deleting any pair if the value becomes zero.
Assuming all hash table operations (i.e., lookup, insert, and delete) take O(1) amortized time, and that enumerating
all key-value pairs in the hash table can be done in time O(k), then this implementation runs in amortized O(1) time
per stream update. This amortized time bound exploits the fact that decrement operations, which require enumerating
all k key-value pairs, only occur at most N/k times.
1.3.3

Description of the Space Saving Algorithm For Unit Weight Updates

When processing a stream update (i, +1), the SS algorithm behaves identically to MG, except in the case where i is
not assigned a counter, and no unassigned counter exists. In this case, SS increments the counter with the smallest
value and assigns it to i. When asked to provide an estimate fˆi for item the frequency of item fi , the algorithm returns
the value of the smallest counter if i is not assigned a counter, and returns the value of the counter assigned to i
otherwise. See Algorithm 2 for pseudocode.

4

Algorithm 2 Space Saving Algorithm for Unit Weight Updates
1: Algorithm: SpaceSaving(k):
2:
T ← ∅ // T is set of items assigned a counter
3: Function Update(i, +1):
4:
if i ∈ T :
5:
c(i) ← c(i) + 1
6:
else if |T | < k:
7:
T = T ∪ {i}
8:
c(i) ← c(i) + 1
9:
else :
10:
j ← arg minj∈T c(j)
11:
c(i) ← c(j) + 1
12:
T = (T \ {j}) ∪ {i}
13: Function Estimate(i):
14:
if i ∈ T :
15:
return c(i)
16:
else
17:
return minj∈T {c(j)}

Efficiently Implementing Space Saving for Unit Weight Updates The SS algorithm can be naturally implemented
by using a min-heap data structure to track the smallest counter at all times. Following [7], we refer to this implementation as SSH. Unfortunately, the use of a min-heap is slow (taking time O(log k) per stream update), and it also nearly
doubles the space usage compared to the MG implementation described above, since both a hash table of capacity k
and a min-heap must be stored.
In the case of unit updates, Metwally et al. [16] propose a doubly linked list based data structure they call Stream
Summary that can process updates in O(1) time. However, the need to store pointers in the linked list will more than
double the space usage of the Misra-Gries implementation described above. Moreover, as mentioned again in Section
1.3.5 below, this implementation method does not naturally extend to weighted updates.
1.3.4

Extending Misra-Gries to the Weighted Case: Prior Work and Its Limitations

There are a number of simple ways to extend the MG algorithm to handle weighted updates. Perhaps the simplest is
to treat an update (ij , ∆j ) as ∆j unit updates. We refer to this as the Reduce-To-Unit-Case (RTUC-MG) extension of
the MG algorithm. However, this takes time at least ∆j per stream update, which is unacceptable when the weights
may be large (this approach is also awkward to apply to the case of non-integer weights).
To our knowledge, the only other proposal to extend the MG algorithm to weighted updates is due to Berinde
et al. [2], who suggest the following modification. Every time the algorithm processes a stream update (ij , ∆j ), the
algorithm looks to see if ij is assigned a counter, and if so it increments the counter by ∆j . If not, and an unassigned
counter exists, the algorithm assigns the counter to i and sets the approximate count to ∆j . If no unassigned counter
exists, the algorithm’s behavior depends on whether ∆j ≤ cmin , where cmin denotes the minimum value of any counter.
If ∆j ≤ cmin , then all stored counters are reduced by ∆j . Otherwise, all counters are reduced by cmin , and some counter
with zero count (there must be at least one now) is assigned to ij and given count ∆j − cmin . We refer to this as the
Reduce-By-Min-Counter (RBMC) extension of the MG algorithm to weighted updates.
It is easy to see that the RBMC algorithm produces estimates identical to the RTUC-MG algorithm, and hence
satisfies the accuracy guarantees of Lemmas 1 and 2. The advantage of the RBMC-MG algorithm is in its runtime,
which does not grow linearly with ∆j . The main shortcoming of the RBMC algorithm is that it still may not run
in amortized O(1) time per stream update. In fact, there are streams on which the proposal will perform expensive
decrement operations on essentially every stream update: consider a stream where the first k updates increment the
counts of distinct items by an arbitrarily large number M , and then the following M stream updates are unit updates
to different items. Decrement operations, each requiring time Θ(k), will be performed on every one of the last M
updates in the stream. While such examples may be contrived, Section 4 provides experimental results on real datasets
showing that the runtime of this algorithm is significantly higher in practice than the alternatives presented in this
5

paper.
1.3.5

Extending Space Saving to the Weighted Case: Prior Work and Its Limitations

The SS algorithm also has a natural Reduce-To-Unit-Case (RTUC-SS) extension to weighted updates. However, like
the RTUC-MG alogrithm, this takes time at least ∆j per stream update, which is unacceptable when the weights may
be large.
The min-heap based implementation, SSH, of SS naturally extends to the weighted case. We refer to this as the
Min-Heap-Extension (MHE) extension of the SS algorithm to weighted updates. However, MHE suffers from the
same poor (i.e., O(log k)) update time and larger space usage (relative to RBMC) as in the unit weight update case.
Despite these shortcomings, this implementation of SS for weighted updates was used in at least one prior work on
computing Hierarchical Heavy Hitters [18].
The implementation of Space Saving that uses the Stream Summary data structure does not naturally extend to the
case of weighted updates [7].
We discuss additional prior work in Section 5.

1.4

Isomorphism Results for Weighted Streams

We mention that the MHE and RBMC algorithms are isomorphic, in the sense that the estimates returned by the MHE
algorithm with k + 1 counters can be derived from the summary computed by the RBMC algorithm with k counters.
This follows immediately from the facts that both the MHE and RBMC produce the same estimates as RTUC-SS and
RTUC-MG respectively, and the latter two algorithms were shown to be isomorphic by Agarwal et al. [1].

2

Our Algorithm

For expository purposes, we first propose an initial modification of the MG algorithm that achieves (up to a constant factor) the same accuracy guarantees as the RBMC algorithm, while guaranteeing O(1) amortized runtime per
stream update. We then describe our final algorithm, which improves over the runtime and space usage of the initial
modification by a factor close to 2.

2.1

An Initial Proposal

For simplicity, we assume throughout this section that k is even. Recall (cf. Section 1.3.4) that the main downside
of the RBMC algorithm [2] is that it does not guarantee O(1) amortized runtime per stream update. The reason was
that RBMC may have to perform decrement operations essentially every stream update, and each decrement operation
requires iterating over k counters.
To guarantee O(1) amortized time per stream update, it is enough to ensure that decrement operations are performed at most once every (say) k/2 stream updates. We mention that a similar technique was used by Liberty to
efficiently identify “frequent directions” in a stream of vectors [12].
To ensure that this property holds, it suffices to consider the following simple modification of RBMC. Every time
the algorithm processes a stream update (ij , ∆j ), the algorithm looks to see if ij is assigned a counter, and if so it
increments the counter by ∆j . If not, and an unassigned counter exists, the algorithm assigns the counter to ij and sets
the approximate count to ∆j . If no unassigned counter exists, the algorithm decrements all counters by the median
counter value cmedian . The algorithm then marks all counters set to a non-positive value as unassigned. If ∆j is larger
than cmedian , then ij is then assigned a counter, which is set to ∆j − cmedian .
We refer to this algorithm as the Reduce-By-Median-Counter (MED) extension of the MG algorithm to weighted
updates. See Algorithm 3 for pseudocode, which is expressed in slightly more general form. Specifically, in Algorithm
3, cmedian is replaced by the the k ∗ ’th largest counter value, where k ∗ is a parameter of the algorithm. One recovers the
description above by setting k ∗ = k/2.

6

Algorithm 3 The Reduce-By-Median-Counter (MED) Extension of the MG Algorithm to Weighted Updates
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:

// Notation: k∗ is a parameter of the algorithm
Algorithm: Initial-Algorithm(k):
T ← ∅ // T is set of items assigned a counter
Function Update(i, ∆):
if i ∈ T :
c(i) ← c(i) + ∆
else if |T | < k:
T = T ∪ {i}
c(i) ← c(i) + ∆
else :
DecrementCounters()
if ∆ ≥ ck∗ // See Line 16 for definition of ck∗
T = T ∪ {i} // |T | ≤ k∗ + 1 ≤ k after this line
c(i) ← c(i) + ∆ − ck∗
Function DecrementCounters():
// Notation: Let ck∗ be the k∗ -largest value, counting multiplicity,
// in the multiset {c(j) : j ∈ T }.
for all j ∈ T :
c(j) = c(j) − ck∗
if c(j) ≤ 0:
T = T \ {j}
Function Estimate(i):
if i ∈ T :
return c(i)
else
return 0

2.1.1

Runtime and Accuracy Analysis

Lemma 3. In Algorithm 3, a DecrementCounters() operation (Lines 15-20) is performed at most once every k ∗ stream
updates.
Proof. Observe that DecrementCounters() operations are performed only when all k counters are assigned. Every time
a DecrementCounters() operation is executed, Line 18 sets at least k ∗ counters to a non-positive value, and all such
counters become unassigned in Line 20. Since any Update(i, ∆) operation assigns at most one counter to i, it follows
that after a DecrementCounters() operation, at least k ∗ Update() operations must occur before all counters once again
become assigned.
Lemma 3 is easily seen to imply that Algorithm 3 can be implemented in O(1) amortized time per stream update.
The main observation is that ck∗ (cf. Line 16) can be found in time O(k) using the Quickselect algorithm [11]. Hence,
decrement operations can be performed in O(k) time, and by Lemma 3, decrement operations occur at most once
every k ∗ = Ω(k) stream updates.
Theorem 1. By maintaining all k counters in a hash table of capacity supporting (amortized) constant time insertions,
deletions, and lookups, and enumeration of all counters in O(k) time, Algorithm 3 can be implemented in amortized
constant time as long as the parameter k ∗ ≥ Ω(k).
It is also not difficult to show that this implementation satisfies the same error guarantee as Lemma 1 up to a factor
of 2. In fact, we prove the following tail guarantee that is significantly stronger than Lemma 1 for streams with skewed
frequency distributions. Our analysis exploits the key ideas of earlier analyses (of the MG algorithm) by Agarwal et
al. [1] and Berinde et al. [2].
Theorem 2. For any j < k ∗ , Algorithm 3 is guaranteed to return, for each i ∈ [n], an estimate fˆi satisfying
0 ≤ fi − fˆi ≤ N res(j) /(k ∗ − j).
7

Proof. It is obvious from the description of the algorithm that 0 ≤ fi − fˆi for all i. To prove the second inequality,
we willP
proceed by induction on the number of stream updates n. For clarity, we introduce some notation. Let
fi,n = j≤n:ij =i ∆j denote the (weighted) frequency of item i in the first n stream updates, and similarly let fˆi,n
denote the output of Estimate(i) after the first n stream updates. Let En = maxi fi,n − fˆi,n denote the P
maximum
error of any estimate that might be returned by the summary after processing n stream updates. Let Cn = Pi∈T c(i)
n
denote the sum of all counts in the summary after the first n stream updates have been processed. Let Nn = i=1 ∆i
denote the weighted stream length after n stream updates.
For expository purposes, we establish the second inequality for j = 0, before establishing it for any j < k ∗ .
Establishing the second inequality for j = 0. In the case j = 0 it is sufficient to show establish the following lemma.
Lemma 4. En ≤ (Nn − Cn )/k ∗ .
Proof. We show this by induction on n. Clearly it holds for n = 0. Assume by way of induction that it holds for
streams consisting of n − 1 updates.
Proof Outline for Lemma 4. The key observations are (a) that error is only introduced by calls to DecrementCounters()
and (b) whenever DecrementCounters() is called, at least k ∗ counters are reduced by ck∗ . Hence, the error in any
estimate increases by ck∗ , and the difference between N and C increases by at least k ∗ · ck∗ . This ensures that the
difference between N and C is always at least k ∗ times the error of the summary, as desired. The rest of the proof
makes this argument formal.
Suppose first that the nth stream update (in , ∆n ) does not cause DecrementCounters() to be called. In this case,
after processing the nth stream update, fin and fˆin both increase by ∆n , and for any i 6= in , fi and fˆi are unchanged.
Hence, En = En−1 , i.e., the error of the summary is unchanged by the nth stream update. Meanwhile, Nn and Cn
both increase by ∆n . It follows that (Nn − Cn ) = (Nn−1 − Cn−1 ). Putting these facts together and invoking the
inductive hypothesis, we conclude as desired that
En = En−1 ≤ (Nn−1 − Cn−1 )/k ∗ = (Nn − Cn )/k ∗ .
Next, suppose that the nth stream update does cause DecrementCounters() to be called. We assume w.l.o.g. that
∆n ≤ ck∗ ; if not, then we instead treat update (in , ∆n ) as two separate updates (in , ck∗ ) followed by (in , ∆n − ck∗ ),
as the algorithm behaves identically in this case.
Then the largest k ∗ counters are each decremented by ck∗ , and no counter is incremented (as Lines 13-14 are not
executed due to the assumption). Hence,
Nn − Cn =Nn−1 +∆n −Cn ≥ Nn−1 +∆n −(Cn−1 −k ∗ · ck∗ )
=Nn−1 − Cn−1 + k ∗ · ck∗ + ∆n
≥Nn−1 − Cn−1 + k ∗ ·ck∗ .

(1)

Meanwhile, it holds that
En ≤ En−1 + ck∗ .
(2)
To see this, first observe that, for all i 6= in , fˆi,n − fˆi,n−1 ≤ ck∗ , and fi,n = fi,n−1 . Hence, fi,n − fˆi,n ≤
fi,n−1 − fˆi,n−1 + ck∗ , i.e., the error in the estimate for i increased by at most ck∗ when processing the nth stream
update.
To see that Equation (2) also holds for in itself, observe first that the fact that DecrementCounters() was called
when processing the nth stream update means that in was not assigned a counter after n − 1 stream updates. Hence,
fˆin ,n−1 = 0. Meanwhile, the assumption that ∆n ≤ ck∗ then ensures that fˆin ,n = 0 as well. And clearly fin ,n =
fin ,n−1 + ∆n . Putting these facts together implies that
fin ,n − fˆin ,n = fin ,n−1 +∆n − fˆin ,n−1 ≤ fin ,n−1 + ck∗ − fˆin ,n−1 .
That is, the error in the estimate for in increased by at most ck∗ when processing the nth stream update. Equation (2)
follows.
8

Combining Equations (1) and (2) with the inductive hypothesis, we conclude as desired that
En ≤ En−1 + ck∗ ≤ (Nn−1 − Cn−1 )/k ∗ + ck∗
≤ (Nn − Cn − k ∗ ck∗ )/k ∗ + ck∗ = (Nn − Cn )/k ∗ .

Establishing the second inequality for any j < k ∗ . For notational simplicity, let us assume that f1 ≥ f2 ≥ · · · ≥ fj .
Lemma 4 implies that
Cn ≤ Nn − k ∗ · En .
(3)
Meanwhile, it is clear that at the end of the stream, c(i) ≥ fi − En for all i, which implies that
!
j
j
X
X
fi − j · En .
Cn ≥
(fi − En ) ≥

(4)

i=1

i=1

Putting Equations (3) and (4) together, we conclude that
!
j
X
fi − j · En ≤ Nn − k ∗ · En ,
i=1

which in turn implies that
(k ∗ − j) · En ≤ Nn −

j
X

fi = N res(j) .

i=1

Hence, En ≤ N

2.2

res(j)

∗

/(k − j). This completes the proof.

The Final Algorithm

Algorithm 3 has two disadvantages that are important in practice. First, an extra k words of space are required during
every DecrementCounters() operation, on top of the Θ(k) words of space required for that hash table that maintains
the counters. This extra space is required in order to find the k ∗ ’th largest counter, as the Quickselect algorithm (or
any sorting procedure) cannot be done in place without destroying the hash table. This disadvantage nearly doubles
the space usage of the algorithm.
Second, during each DecrementCounters() operation, the algorithm must make an extra pass through the summary
to find the k ∗ ’th largest counter, before decrementing all counters and discarding the non-positive ones. As DecrementCounters() operations is the time bottleneck in practice, this significantly slows the concrete efficiency of the
algorithm.
In order to address both of these disadvantages at once, we make the following observation. In neither the proof of
Theorem 1 (establishing constant amortized update time for Algorithm 3) nor Theorem 2 (establishing strong bounds
on the error of Algorithm 3) is it crucial that we decrement by the k ∗ ’th largest counter value for k ∗ = k/2. The
property that ensures constant amortized update time as per Theorem 1 is that each DecrementCounters() operation
decrements by a value that is larger than a constant fraction of the counters. The property exploited to establish the
error bounds of Theorem 2 is that each DecrementCounters() operations decrements by a value that is smaller than a
constant fraction of the counters.
Both properties can be ensured by modifying the DecrementCounters() function as follows. We randomly sample
` counters in the hash table, where ` = O(log n) is a suitably chosen parameter. We then compute the median of
the sampled counters, and decrement all counters by this value, discarding any counters that are non-positive after
decrementing. We refer to this algorithm as the Reduce-By-Sample-Median (SMED) extension of the MG algorithm.
See Algorithm 4 for pseudocode.
Theorem 3. There is an ` = O(log n) such that Algorithm 3 can be implemented to run in amortized constant time
with probability at least 1 − 1/n.
9

Algorithm 4 The Reduce-By-Sample-Median (SMED) Extension of the MG Algorithm to Weighted Updates
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:

// Notation: k∗ is a parameter of the algorithm
Algorithm: Initial-Algorithm(k):
T ← ∅ // T is set of items assigned a counter
Function Update(i, ∆):
if i ∈ T :
c(i) ← c(i) + ∆
else if |T | < k:
T = T ∪ {i}
c(i) ← c(i) + ∆
else :
DecrementCounters()
if ∆ ≥ c∗ // See Line 17 for definition of c∗
T = T ∪ {i} // |T | ≤ k∗ + 1 < k after this line
c(i) ← c(i) + ∆ − c∗
Function DecrementCounters():
// Notation: ` is a parameter
// Randomly sample ` counters from T
// and let c∗ be the median of the samples.
for all j ∈ T :
c(j) = c(j) − c∗
if c(j) ≤ 0:
T = T \ {j}
Function Estimate(i):
if i ∈ T :
return c(i)
else
return 0

Proof. Standard Chernoff bounds (e.g., [19, Theorem 4.4]) imply that if ` ≥ c · log n for a suitably large constant
c > 0, then with probability at least 1 − 1/n2 the median c∗ of ` counters sampled from {c(i) : i ∈ T } will satisfy
c∗ ≥ c(i) for at least k/3 values of i (where recall that k = |T | whenever a DecrementCounters() operation occurs).
By a union bound, we conclude that this event occurs for all DecrementCounters() operations with probability at least
1 − 1/n. In this event, DecrementCounters() operations occur at most once every k/3 stream updates. The claimed
time bound now follows from the same argument as in Theorem 1.
Theorem 4. For any constant c > 2, there is an ` = O(log n) such that the following holds with probability at least
1 − 1/n. For any j < k/c, Algorithm 4 will return, for each i ∈ [n], and estimate fˆi satisfying
0 ≤ fi − fˆi ≤ N res(j) /(k/c − j).
Proof. It is easy to see that the proof of Theorem 2 applies even if Algorithm 4 decrements all counters by at most
ck∗ rather than exactly ck∗ . Hence, it suffices to show that for any constant c > 2, there is an ` = O(log n) such that
with probability at least 1 − 1/n2 , the median c∗ of ` counters sampled from {c(i) : i ∈ T } satisfies c∗ ≤ c(i) for at
least k/c values of i ∈ T . Indeed, this property holds by standard Chernoff bounds [19, Theorem 4.4]. By combining
this property with a union bound over all DecrementCounters() operations, we conclude that with probability at least
1 − 1/n, Algorithm 4 always decrements all counters by at most ck∗ where k ∗ = k/c.

2.3

Additional Implementation Details

We have completed a highly optimized implementation of Algorithm 4 in Java and incorporated it into an open source
library [20] that is widely deployed within Yahoo and several other companies. We briefly present additional details
of our implementation not covered above.
10

2.3.1

Variant of Function Estimate()

In our implementation, we modified the function Estimate() compared to the pseudocode of Algorithm 4. Specifically,
our implementation keeps a variable offset that tracks the sum of all decrement values c∗ over all DecrementCounters()
operations. If i is assigned a counter, then our implementation’s estimate fˆi for fi is c(i) + offset. If i is not assigned
a counter, the returned estimate is 0.
This represents a hybrid of the estimates returned by the MG and SS algorithms (cf. Algorithms 1 and 2 respectively). It behaves analogously to the MG algorithm on items i not assigned counters – outputting 0 in this case – and
(as explained below) analogously to the SS algorithm on items i that are assigned counters.
Our reasoning for this choice is as follows. Before the MG and SS algorithms were realized to be isomorphic [1],
Cormode and Hadjieleftheriou [7] found that the estimates returned by SS were superior in practice, despite the fact
that the worst-case error bounds for both algorithms are essentially identical. The reason for this is that the SS estimates
are “more aggressive” – in particular, whereas the MG algorithm will always strictly underestimate the frequency of
an item (unless fewer than k items appear in the stream), the SS algorithm may well output exactly correct estimates
of frequent items. The estimates returned by our actual implementation inherit this desirable property of SS.
On the other hand, the SS algorithm has the undesirable property that it will always strictly overestimate the
frequency of an item that does not appear in the stream (unless fewer than k items appear in the stream), whereas the
MG algorithm always outputs exactly correct estimates (namely, 0) for such items. The estimates returned by our
actual implementation inherit this desirable property of MG.
We remark that, like MG and SS themselves, our implementation is also capable of outputting tight upper and
lower bounds on the frequency of i. The upper bound is c(i) + offset, while the lower bound is c(i) (or 0 if i is not
assigned a counter).
2.3.2

Choice of `

We performed numerical calculations establishing that the choice ` = 1024 guarantees that the following holds. For
streams of length N ≤ 1020 , Algorithm 4, with probability at least 1 − 1.5 × 10−8 , returns estimates fˆi for all i ∈ [m]
satisfying the following error guarantee:
0 ≤ fi − fˆi ≤ N res(j) /(.33 · k − j).
Hence, we set ` = 1024 in our implementation.
2.3.3

Hash Table and Exact Space Usage

We experimented with a wide variety of hash table implementations for storing counters. While many performed
similarly, we discovered that a good choice is to use linear probing. Specifically, keys and values are kept in two
parallel arrays of length L ≈ 4k/3 (the length is rounded up to the closest power of two to ensure fast modular
arithmetic on indices into the arrays, in case a probe “falls off the end” of the array). We keep an additional array of
state variables, where a state of 0 indicates that a cell is unoccupied, and a positive state equals the distance (plus one) of
the stored key x from its preferred cell h(x), where h : [m] → L is the hash function. Insertion and lookup operations
are processed as in standard linear probing: the implementation successively looks at cells h(x), h(x)+1(mod L), . . . ,
until the key is found or an empty cell is discovered.
The other functionality that must be supported by our hash table is decrementing all values by a specified amount
c∗ and deleting all that become non-positive. This is done by starting at the end (i.e., largest index) of a run (i.e., a
contiguous sequence) of occupied cells; each time a non-positive value is identified, the implementation deletes it, and
then works its way toward the end of the run, shifting keys and values forward as necessary to ensure that all future
lookup and insert operations behave correctly.
State variables need only consist of 2 bytes with overwhelming probability (we performed numerical calculations
showing that when k ≤ 232 and L = 4k/3, the probability that at any given time a state variable exceeds 214 is at
most 10−250 ). Hence, assuming item identifiers and approximate counts are 8 bytes each, and that 4k/3 is a power of
2, our implementation uses 18 · (4/3) · k = 24 · k bytes, plus a small constant number of additional bytes.

11

3

Merging Summaries

An extremely important functionality in real systems is the ability to efficiently merge the summaries of separate
data sets (via an arbitrary aggregation tree) to obtain a summary of the union of the data sets, without increasing the
size of the summary or its approximation error. This mergeability property enables a wide variety of scenarios. For
example, consider a system that keeps a separate summary for many subsets of a large dataset. This might occur if,
e.g., a company keeps a separate summary for data obtained in each 1-hour period over the course of several years.
The company may further subdivide the data by, say, geographic region or other attributes. At query time, an analyst
can specify which data are of interest (e.g., the analyst may be interested in users from a given state who used the
company’s service in a given 48-hour window). The summaries can then be seamlessly merged to answer approximate
queries about the data of interest. In this important example, merging is occurring at query time, and millions or
billions of summaries may need to be merged to answer the query. Hence, merging must be extremely efficient,
justifying our focus in this section on developing a highly optimized merging procedure.
As a second example, mergeable summaries enable a single large dataset to be partitioned arbitrarily among many
machines, with each machine processing each partition separately. The resulting summaries can then be merged in any
order to obtain a summary for the complete dataset. Hence, mergeable summaries enable datasets to be automatically
processed in a parallel and distributed manner.
As a final example, consider multiple datasets that are geographically distributed. It may be infeasible to transmit
the entirety of any one of the datasets to a central machine. If an analyst is interested in the union of the datasets,
mergeable summaries enable each dataset to be summarized separately, and merely the summaries transmitted to one
machine.

3.1

Earlier Merging Procedures

The Procedure of Berinde et al. [2] The merging procedure we describe in this section is highly similar to a proposal
of Berinde et al. [2], who described their proposal in the context of arbitrary counter-based summaries. Berinde et al.
suggested that, in order to merge many summaries, one should treat each counter in each summary as a stream update
(so a counter c(i) assigned to item i is treated as a stream update (i, c(i))) and feed all the stream updates into a single
new summary. They proved that if the counter-based algorithm when run on a single stream can return estimated
frequencies fˆi for each i satisfying |fi − fˆi | ≤ N res(j) /(k − j), then the output of the merging procedure can return
estimated frequencies fˆi satisfying
|fi − fˆi | ≤ 3 · N res(j) /(k − 2j),
(5)
where the quantities fi and N res(j) in Equation (5) refer to the concatenation of the streams that were fed into each of
summaries being merged.
The proposal and accuracy analysis of Berinde et al. [2] have two significant limitations. First, the accuracy
analysis only guarantees that the merged summary has at most triple the error of the constituent summaries. Second,
as pointed out in [1], when merging many summaries, the proposal does not support an arbitrary aggregation tree (i.e.,
it is not possible to repeatedly merge pairs of summaries in an arbitrary manner until a single summary is obtained).
Rather, each summary must be merged “into” a single output summary. This second limitation is really a different
manifestation of the first: the reason that Berinde et al. cannot support an arbitrary aggregation tree is that their error
analysis cannot rule out the possibility that each edge in the tree causes a tripling of the error. Hence, the final error
bound for an arbitrary aggregation tree would be exponentially large in the number of summaries being merged.
The merging procedure we propose in this section is closely related to that Berinde et al. However, we address
both of the limitations above by giving a much tighter error analysis. Moreover, since our merging procedure uses
our algorithms’ Update(i, ∆) procedure as a black box, it inherits the benefits of our Update(i, ∆) procedure (e.g.,
amortized constant runtime) relative to prior algorithms for weighted streams.
Our procedure has the additional advantage of not requiring the allocation of a new output summary for a merge;
rather, when merging two summary via our procedure, we seamlessly update the state of one of the two summaries
and output the result (discarding the other summary once merging is complete).
We mention in passing that other merging procedures for frequent items algorithms have been proposed [13, 14],
but they provide weaker error guarantees than Berinde et al. (i.e., the error increases with each merge step).

12

Algorithm 5 Our Merge Procedure
1:
2:
3:
4:
5:
6:
7:

// Notation: T1 , T2 are both counter-based summaries,
// i.e., T2 is a set of items i and approximate counts c(i), and
// T1 comes with an UpdateT1 () procedure.
Function: Merge(T1 , T2 ):
for each i ∈ T2 :
UpdateT1 (i, c(i))
return T1

The Procedure of Agarwal et al. [1] Agarwal et al. [1] provided a merging procedure for the MG and SS algorithms
that does support arbitrary aggregation trees. In this discussion, we focus on the case of the MG algorithm for
simplicity. To merge two MG summaries with k counters each, their merging procedure works as follows. The
counters from each summary are first added together (so if an item i is assigned a counter in both summaries, its count
is set to the sum of the two counters). The counters are then sorted, and all but the top k counters are discarded.
Suppose that for j = {1, 2}, the j’th MG summary is a summary of a stream σj of weighted length Nj , and let
N = N1 + N2 denote the weighted length of the concatenated stream σ := σ1 ◦ σ2 . Let fi denote the frequency of i
in σ. Agarwal et al. proved that the resulting summary returns estimates fˆi for all i such that:
0 ≤ fi − fˆi ≤ (N − C)/(k + 1),

(6)

where C is the sum of the counters in the merged summary.
Implementing the Merging Procedure. The natural way to implement the merging procedure of Agarwal et al. is the
following. First, allocate a new hash table capable of storing up to 2k counters. Second, iterate through the counters
(i, c(i)) in both summaries, adding all (i, c(i)) pairs into the new hash table (if key i already resides in the hash table,
then add c(i) to its value). This has the effect of summing counters. Third, sort the (i, c(i)) pairs in the hash table
by c(i). Fourth, create a new summary of capacity k and insert the top k (i, c(i)) pairs into the summary, discarding
earlier summaries and the intermediate hash table used for merging.
We observe that an alternative implementation of the third and fourth steps above is to use Quickselect [11] to
identify the kth largest counter ck in the hash table. One then makes an additional pass through the counters, identifying
all that are at least as large as ck , and feeding each into the new summary. This implementation runs in time O(k).
Disadvantages. This merging procedure has a number of disadvantages in practice. First, it requires allocating a hash
table of capacity 2k to add the counters, which potentially doubles the combined space usage of the two constituent
MG summaries. Second, the original sorting-based proposal of Agarwal et al. requires Ω(k log k) time. As we
observe above, one can use Quickselect to reduce the runtime to O(k), but the Big-Oh notation hides a substantial
constant factor, and running Quickselect on up to 2k counters is a runtime bottleneck in practice. Third, while this
merging procedure easily extends to the case where the two summaries have differing numbers of counters (say k1 and
k2 counters respectively), it requires Ω((k1 + k2 ) · log(k1 + k2 )) time. One can hope to achieve O(min(k1 , k2 )) time.
In this section, we give a different merging procedure that mitigates these disadvantages. Our procedure applies
generically to any counter-based algorithm that can efficiently handle weighted updates. We now describe the procedure in this level of generality.

3.2

Our Merging Procedure

Description of our Merging Procedure For simplicity, let us assume that both summaries to be merged are configured to store k counters. Let k 0 denote the number of (non-zero) counters in the second summary to be merged. In
our merging procedure, the k 0 non-zero counters from the second summary are treated as k 0 stream updates, and each
stream update is fed into the first summary using the summaries Update() procedure. That is, for each item i assigned
a counter c(i) in the second summary, then the function Update(i, c(i)) is called on the first summary. See Algorithm
5 for pseudocode.

13

Space Usage Clearly, this merging procedure avoids the 2k extra words of space (on top of the space to store the
two summaries being merged) required by the merging procedure of Agarwal et al. [1]. It uses no more space than that
already used by the two summaries being merged, seamlessly updating the state of one of the summaries, outputting
the result, and discarding the other summary upon completion.
Speed We can guarantee that our merging procedure runs in time O(k). This follows from the fact that the Update()
operation for our algorithms take O(1) time unless a DecrementCounters() operation is triggered, and a DecrementCounters() operation takes O(k) time and is triggered at most once every Ω(k) stream updates.
One might hope that if k 0  k (which will be the case, e.g., if the second summary is significantly smaller than
the first), then the merging procedure runs in O(k 0 ) time. Unfortunately, we cannot quite provide this guarantee. For
example, if the second summary contains only a single nonzero counter c(i), and calling Update(i, c(i)) on the first
summary triggers a DecrementCounters() operation, then the merging procedure will take Θ(k) time. However, we
can guarantee the following. If Ω(k/k 0 ) summaries of size at most k 0 are merged into a single summary of size k, then
the amortized time per merge is O(k 0 ).
Error We now show that our merging procedure, when applied to our MED algorithm (Algorithm 3) satisfies an
error property analogous to that established by Agarwal et al. (cf. Equation (6)). Using similar ideas, it can be shown
that our merging procedure satisfies the analogous guarantees when applied to Algorithm 4, but we omit this result for
brevity. While our merging procedure satisfies many desirable properties compared to that of Agarwal et al. [1], our
error analysis exploits the same key ideas as theirs.
Theorem 5. Suppose that for j = {1, 2}, we run Algorithm 3 with k counters on a stream σj of weighted length Nj .
Let N = N1 + N2 denote the weighted length of the concatenated stream σ := σ1 ◦ σ2 . Let fi denote the frequency
of i in σ. Then after applying the merging procedure of Algorithm 5, the resulting summary can, for any i, return an
estimate fˆi satisfying
0 ≤ fi − fˆi ≤ (N − C)/k ∗ ,
(7)
where C is the sum of the counter values in the merged summary. In fact, for any j < k ∗ , it holds that
0 ≤ fi − fˆi ≤ N res(j) /k ∗ .

(8)

Proof. Clearly 0 ≤ fi − fˆi for all i. We now turn to establishing that fi − fˆi ≤ (N − C)/k ∗ .
For j ∈ {1, 2}, let fˆi,j denote the estimate for i returned by summary j after being run on σj , and let fi,j denote
the true frequency of item i in σj . Let Ej := maxi fi,j − fˆi,j , and let c(j) denote the sum of the counter values
in summary j after being run on σj . Let E = maxi fi − fˆi denote the maximum error in any estimate returned by
the merged summary. Finally, let S denote the sum of all values ck∗ that are computed during DecrementCounters()
operations called during the merge procedure.
It is clear that E ≤ E1 + E2 + S. By Lemma 4,
E ≤ (N1 − C1 )/k ∗ + (N2 − C2 )/k ∗ + S.

(9)

Recall from the proof of Lemma 4 that any DecrementCounters() operation decreases at least k ∗ counters by ck∗ .
Hence, S ≤ (C1 + C2 − C)/k ∗ . Combining this with Equation (9), we conclude that E ≤ (N1 − C1 )/k ∗ + (N2 −
C2 )/k ∗ + (C1 + C2 − C)/k ∗ = (N1 + N2 − C)/k ∗ = (N − C)/k ∗ , establishing Equation (7). To see that Equation
(8) follows from Equation (7), use the same argument from the proof of Theorem 2 (as the proof of Theorem 2 showed
that the desired tail guarantee follows in a black box manner from Lemma 4).
We remark that a final advantage of our merging procedure is that it does not require significant additional code on
top of the streaming algorithm itself: it simply invokes the streaming algorithm’s Update() procedure in a black-box
manner.
Note. A subtlety regarding implementations of our proposed merging procedure is as follows. If counters are stored
in hash tables, then the performance guarantees of the hash table assume that hash values are (roughly) uniformly
distributed throughout the table. If our merge procedure is used to merge two summaries whose hash tables use the
14

same hash function, then care must be taken to ensure that this property continues to hold. For example, if one iterates
through the second summary’s hash table from front to back, calling Update(i, c(i)) on the first summary for each
counter (i, c(i)) encountered, then one may “overpopulate” the front of the first summary’s hash table.
One avoids this issue entirely if the summaries choose their hash functions independently of each other. Even
for summaries that do use the same hash function, this issue can be addressed by, say, iterating through the second
summary’s counters in a random order.

4

Experiments

The goal of this section is to investigate three issues. First, we compare our main algorithm SMED to alternatives:
the proposals RBMC and MHE of prior work, and a variant of SMED that we call SMIN. The difference between
SMIN and SMED is that the DecrementCounters() operation of SMIN decrements all counters by the sample minimum counter value, instead of the sample median value. Notice that SMIN is identical to RBMC, except that the
DecrementCounters() operation of RBMC decrements by the global minimum counter value, while SMIN decrements
by the minimum counter value in a sample of size ` = 1024.
We find that SMED is significantly faster than the the algorithms of prior work (5.5x-8.7x faster than MHE and
up to 70x faster than RBMC). While it is not quite as accurate as MHE or RBMC for a given amount of memory,
the maximum error of SMED is at most 30% larger than that of MHE, and less than 2.5x that of RBMC and SMIN
(the latter two algorithms had nearly identical error on the datasets used in our experiments). Moreover, the increased
error of SMED relative to alternatives can be overcome, while simultaneously decreasing runtime, by increasing the
number of counters by a small factor (less than 2x). This is entirely expected, as our error analysis (cf. Theorems 2
and 4) indicate that for sufficiently large settings of the parameter `, SMED with k counters has error that is no worse
than RBMC with ≈ k/2 counters. Hence, we find that our novel SMED algorithm is the preferable option, except
possibly in settings where space and accuracy are paramount.
Even in settings in which space and accuracy are paramount, we find that on the datasets with which we experimented, the preferable solution is our novel algorithm SMIN. For a given space bound, SMIN achieves error nearly
identical to RBMC (and much better than MHE), with far superior speed.
Second, our main algorithm SMED (cf. Algorithm 4) naturally allows for a smooth tradeoff between error and
speed as follows. While SMED itself implements the DecrementCounters() procedure by sampling many counters
and decrementing by the sample median, one could instead decrease by a different sample quantile (at the extreme
end is SMIN, which decrements by the sample minimum). A larger decrement amount increases the error, but ensures
that DecrementCounters() operations occur less frequently, and hence speeds up the algorithm. We investigate this
tradeoff on real and synthetic datasets, and find that decrementing by sample medians is indeed an attractive point on
this tradeoff curve.
Third, we compare our merging procedure to prior work [1], and find that ours is significantly faster (up to 12x
faster than a straightforward implementation of prior work [1]) while using less than half the space.

4.1

Details

All experiments were run on a machine running Windows 10 with a Intel Core i5-6600K 3.5GHz Quad-Core Processor,
(2 x 8GB) DDR4-2666 Memory, and a 500GB SSD. Test data was generated from the CAIDA Anonymized Internet
Traces 2016 Dataset. Four packet capture files were chosen at random from the dataset. These were then preprocessed
into updates of the form (ai , ∆i ), where ai is the source IP with decimal points excluded, and ∆i is the packet size in
bits. These four preprocessed streams were then concatenated
into one larger stream. The stream length was n ≈ 126.2
Pn
million and the weighted stream length was N := i=1 ∆i ≈ 72.2 × 109 . Since the data came from an IPv4 packet
capture, the universe size is m = 232 . Although IPv4 addresses can be stored with 32 bits, our implementations, for
purposes of generality, use a long long data type (64 bits) to store each. The implementations can be trivially modified
to only use 32 bits per identifier if desired.
The number of unique identifiers in the packet stream was approximately 1.75 million. This may seem small, as
the trivial (exact) algorithm that keeps a hash table storing an exact count for each unique IP address in the stream will
use only several dozen megabytes of space. Nonetheless, this is more than enough data to obtain a clear qualitative
15

Figure 1: Runtime Comparison of Four Algorithms
comparison of the tested algorithms. Moreover, our new algorithms, when run with, say, k = 24, 576 counters, use
less than 1/70th of the space of the trivial solution.
We also ran experiments on synthetic data generated by a Zipfian distribution with various skewness parameters.
The algorithms performed entirely similarly on these datasets and the packet trace data. Hence, for brevity we only
present our experimental results on the packet trace data.

4.2

Properties Exhibited By All Algorithms

For any fixed stream, as the number of counters k used in a counter-based algorithm increases, the algorithm grows
closer and closer to being exact, and the number of DecrementCount() operations relative to the number of stream
updates decreases. Hence, the algorithms’ performances (in both speed and error) converge as the number of counters
grows. Consequently, the biggest differences between the counter-based algorithms explored in our experiments are
observed when the number of counters is relatively small.

4.3

Comparison to Baselines

We compared our new algorithms, SMED and SMIN, to the algorithms for weighted streams given in prior work,
RBMC and MHE. While RBMC, SMED, and SMIN all use the same amount of space (in bytes) for a given number

16

Figure 2: Maximum Error Comparison of Four Algorithms. RBMC is omitted from both plots, as its error is indistinguishable from SMIN. For an equal number of counters k (bottom plot), RBMC, MHE, and SMIN all have
indistinguishable maximum error, and hence only one is displayed. Indeed, RBMC with k counters is isomorphic to
MHE with k + 1 counters, cf. Section 1.4.
of counters k, MHE uses additional space owing to the need to maintain a min-heap data structure in addition to a hash
table storing all counters. Figures 1 and 2 present both equal-space and equal-counters comparisons of the algorithms.
For each of our five tested values of k, we ran each algorithm 10 times on the same packet stream, and all numbers
reported are averages of all 10 runs (the error and space usage for the MHE and RBMC algorithms are deterministic
functions of the stream, so only the timings varied from run to run for these algorithms).
Figures 1 and 2 show runtime and maximum error comparisons for the four algorithms. Only the runtime graphs
contain the results for RBMC, because the error of RBMC and SMIN were so close as to be indistinguishable.
Comparison of SMED to Alternatives. Figure 1 demonstrates that SMED significantly outperforms all three alternatives in terms of runtime. For an equal amount of space, SMED was faster than MHE by a factor of 5.5x-8.7x.
Compared to SMIN, SMED was 6.5x-30x faster, and compared to RBMC, SMED was 20x-70x times faster. As
indicated in Section 4.2, the smaller the number of counters k, the faster SMED is relative to the alternatives.
Figure 2 demonstrates that for, an equal amount of space, the maximum error of SMED is only 18%-29% larger
than that of MHE. RBMC and SMIN both have significantly less error than SMED and MHE for a given amount
of space. However, the maximum error of SMED is never more than 2.5x that of RBMC and SMIN. Moreover, the
figure demonstrates that this increased error of SMED relative to alternatives can be overcome (while simultaneously
decreasing runtime) by increasing the number of counters (and hence space consumption) by a factor of less than 2x.
In conclusion, SMED appears to be the most attractive option, except in settings where space and error are significantly more important than speed. In these settings, our new SMIN algorithm is more attractive than the alternatives
from prior work, namely MHE and RBMC (we note that Section 4.4 below demonstrates that it is possible to smoothly
interpolate between SMED and SMIN, obtaining different tradeoffs between speed and error. Exactly which tradeoff is preferable depends on the relative importance of speed vs. error in the application domain). Figures 1 and 2
demonstrate that for an equal amount of space, SMIN is about 2x faster than RBMC, and their error behaviors are
indistinguishable. For an equal amount of space, SMIN is never more than 2x slower then MHE and is actually faster
than MHE for large k; meanwhile, the error of MHE is 1.6x-1.8x that of SMIN.

4.4

Tradeoffs Between Speed and Error

Recall that SMED takes a sample of the keys currently being stored in the hash table, uses Quickselect [11] to compute
the median of the sample, then decrements all counters by this quantity. We ran tests on a large number of variations

17

of this novel algorithm, where a variation might decrement by other sample quantiles rather than the sample median.
Overall, we tested fifty total variations, ranging from the 0th quantile to the 98th quantile. Note that decrementing by
the 0th quantile yields the algorithm SMIN.
The leftmost plot in Figure 3 shows the runtime in seconds for each setting of k, and how it varies with the quantile
used to determine decrements. The runtimes for SMIN and a few other low quantiles are not displayed so as not to
distort the graph, as those runtimes are significantly larger than the rest. This is expected, as the less aggressively
DecrementCounters() decreases counter values, the greater the number of DecrementCounters() operations that occur. From the 0th quantile (SMIN) to the 50th quantile (SMED), runtime drops heavily (specifically, as indicated
previously in Section 4.3, SMED is 6.5x-30x faster than SMIN, depending on number of counters k.) Trivially the
best runtimes are achieved by using very high quantiles in the DecrementCounters() operation, but the “returns” are
diminishing: using the 98th quantile yields an algorithm that is only 20-30% faster than using the the 20th quantile.
The middle and bottom plot in Figure 3 displays the relationship between quantile and maximum error. As expected, the trend here is that as quantile increases, error increases. However, the error increases relatively slowly as the
quantile increases from 0 to about 70, before shooting up rapidly thereafter. We conclude that, on the datasets tested,
any quantile less than roughly 70 represents a reasonable choice in the tradeoff curve between speed and error; exactly
which point on the curve is most desirable will depend on the relative importance of speed vs. error in an application.
We believe, however, that it is wise to always use a quantile of roughly 10 or higher (i.e., we believe this is preferable to using SMIN). Such a choice of quantile achieves almost all of the accuracy advantages of SMIN, while coming
with significantly improved worst-case runtime bounds compared to SMIN. In particular, this provides runtime guarantees even for data distributions that differ substantially from any that we experimented on.

4.5

Merging

In addition to the prior tests, we also ran experiments to evaluate our merging procedure (cf. Section 3). We compared
our proposed procedure against the proposal of Agarwal et al. [1], as well as the variant that we proposed (cf. Section
3.1) that uses Quickselect [11] rather than sorting to identify the kth largest counter after “adding” the counters from
the two sketches being merged. Recall that our merging procedure uses the Update() operation of a counter-based
algorithm as a black box; we tested our merging procedure using the Update() procedure of SMED.
In each of our experiments, we merged 50 pairs of sketches, with each sketch having a capacity of k counters.
These experiments require 50x the amount of raw data that is required to test a single sketch. Hence, we “filled up”
the sketches using synthetic data streams before merging them: the streams had item identifiers drawn from a Zipfian
distribution with parameter α = 1.05, and item wieghts were generated from a uniformly random distribution from 1
to 10,000 (cf. [2, Section 5] for a definition of this distribution).
As illustrated in Figure 4, when using SMED, our proposed merging procedure runs up to 8.6x-10x faster than
the procedure of [1] (the bigger the sketch, the faster our proposed procedure is relative to that of [1]). Our proposed
merging procedure is 1.9x-2.26 faster than the Quickselect-based variant. Moreover, the error of our merge procedure
when using SMED was always within 2.5% of the error of the procedure of [1] and the equivalent Quickselect-based
variant; owing to the small magnitude of this difference, we do not display this error graphically.
It is worth mentioning that our proposed merge algorithm also uses less space than the two alternatives. Both
alternatives require allocating an additional hash table of capacity 2k in order to store all counters from both sketches,
as well as an extra hash table of capacity k to store the final merged sketch. Hence, they consume 2.5x more space
than our procedure, which uses no additional space beyond that already used by the two sketches to be merged.

5

Other Prior Work

Work of Bhattacharyya et al. Recent work of Bhattacharyya et al. [3] gives improved space bounds for identifying
(φ, ε)-heavy hitters in the `1 norm for insertion streams. They describe their algorithms in the context of unweighted
streams. Roughly speaking, for any constant failure probability δ > 0, their algorithms manage to replace the log n
factor in the O(ε−1 · log n) space bound (in bits) for the basic MG and SS algorithms with a factor of log(φ−1 ), which

18

Figure 3: Time and error of our algorithms as a function of the quantile Used by DecrementCounters(). The middle
and bottom plots are identical, except that the bottom plot cuts off large quantiles in order to better illustrate the error
for small quantiles.

19

Figure 4: Speed of Our Merge Procedure Compared to Prior Work. ACH+13 denotes a direct implementation of
the merging procedure of Agarwal et al. [1]. Hoa61 denotes our proposed Quickselect-based implementation of the
procedure of [1] (cf. Section 3.1).
is asymptotically optimal.2
They give two algorithms for identifying (φ, ε)-heavy hitters: a relatively simple algorithm that is nearly spaceoptimal (it is sub-optimal only because it replaces the log n factor in the space bound of MG and SS with a factor of
log(ε−1 ) instead of log(φ−1 )), and a significantly more complicated algorithm that achieves asymptotically optimal
space usage.
Their simple algorithm works by sampling O(ε−2 log(1/δ)) stream updates at random, and feeding the sampled
updates into a (slightly modified) instance of the MG algorithm with k = O(1/ε) counters. The samples are computed
implicitly in O(1) time per stream update by “skipping” each stream update with probability 1 − p, for a parameter
p = O(ε−2 log(1/δ)/n). To save space, the counters in the MG algorithm do not store full item identifiers. Instead,
they each store a hash (consisting of O(log 1/ε) bits) of the assigned identifier; a separate table is used to track
the actual identifiers corresponding to the φ−1 largest counters in the MG summary. For such identifiers, estimated
frequencies in the sample (scaled appropriately) are used as estimates for their true frequencies.
Some thought is required in order to extend this idea to the setting of weighted streams while maintaining constanttime updates. Trivially, one can treat an update (i, ∆) as ∆ updates of the form (i, 1), but this does not maintain the
time bound (even in an amortized sense) if ∆ = ω(1) on average. We now sketch an adaptation that has the same
accuracy guarantees as the simple algorithm of Bhattacharyya et al. [3], and runs in constant amortized time per stream
update with high probability, assuming that the number
of stream updates n is Ω(ε−2 log(1/δ)).
P
Assume the weighted stream length N =
i fi is known in advance (this assumption can be removed using
observations of [3, Section 3.5]). Fix a suitable p = O(ε−2 log(1/δ)/N ). When processing update (i, ∆), the
streaming algorithm repeatedly samples geometric random variables with parameter p (i.e., the variables are distributed
according to the number of Bernoulli trials with success probability p that are needed to get one successful trial). It
stops when the sum of the variables is more than ∆. If t samples are required before the sum of the variables is
more than ∆, then the algorithm feeds update (i, t) into an instance of any counter-based algorithm capable handling
weighted updates. The remainder of the details, and the error analysis, are similar to [3], and we omit them for brevity.
The above adaptation allows our efficiency improvements relative to prior work for weighted streams and mergeability to carry over in a black-box manner to the simple algorithm of Bhattacharyya et al. [3]. One simply feeds the
(weighted) sampled stream updates into our new optimized algorithms for weighted updates.
2 The

precise space bound they achieve for constant failure probability δ > 0 is, in our notation, O(ε−1 · log(φ−1 ) + φ−1 · log m + log log n)

bits.

20

Work of Bhattacharyya et al. Recent independent work of Sivaraman et al. [21] proposes modifying the SS algorithm (cf. Section 1.3.3) as follows. When processing a stream update (i, ∆), if i is not assigned a counter and all
counters are in use, sample ` counters at random (where ` is a design parameter), and then reassign this counter to i and
increment it by ∆. The primary motivation for this proposal is to minimize memory accesses on each stream update,
as memory accesses are a bottleneck in network switching hardware. For ` = O(1), this proposal runs in constant
time per stream update, but may have larger error than our proposals. We leave a detailed experimental comparison of
our algorithms with the proposal of Sivaraman et al. [21] to future work.

6

Conclusion

We described a highly optimized version of Misra and Gries’ seminal algorithm for estimating frequencies of items
over data streams. Our algorithm improves on two theoretical and practical aspects of prior work. First, it handles
weighted updates in amortized constant time. Second, it uses a simple and fast method for merging summaries that
asymptotically improves on prior work even for unweighted streams.
One direction for future work is to incorporate our optimized algorithms into more complicated streaming algorithms that use heavy hitter algorithms as subroutines. These include estimating the empirical entropy of a data
stream [5], and identifying hierarchical heavy hitters [18].
Acknowledgements. We are grateful to Graham Cormode for helpful comments on an earlier version of this manuscript.

References
[1] P. K. Agarwal, G. Cormode, Z. Huang, J. M. Phillips, Z. Wei, and K. Yi. Mergeable summaries. ACM Trans.
Database Syst., 38(4):26, 2013.
[2] R. Berinde, P. Indyk, G. Cormode, and M. J. Strauss. Space-optimal heavy hitters with strong error bounds. ACM
Trans. Database Syst., 35(4):26, 2010.
[3] A. Bhattacharyya, P. Dey, and D. P. Woodruff. An optimal algorithm for `1 -heavy hitters in insertion streams and
related problems. In Proceedings of PODS, pages 385–400, 2016.
[4] V. Braverman, S. R. Chestnut, N. Ivkin, and D. P. Woodruff. Beating countsketch for heavy hitters in insertion
streams. In Proceedings of STOC, pages 740–753, 2016.
[5] A. Chakrabarti, G. Cormode, and A. McGregor. A near-optimal algorithm for estimating the entropy of a stream.
ACM Trans. Algorithms, 6(3), 2010.
[6] M. Charikar, K. Chen, and M. Farach-Colton. Finding frequent items in data streams. In Proceedings of ICALP,
pages 693–703, 2002.
[7] G. Cormode and M. Hadjieleftheriou. Methods for finding frequent items in data streams. VLDB J., 19(1):3–20,
2010.
[8] G. Cormode, F. Korn, S. Muthukrishnan, and D. Srivastava. Diamond in the rough: Finding hierarchical heavy
hitters in multi-dimensional data. In G. Weikum, A. C. König, and S. Deßloch, editors, Proceedings of the ACM
SIGMOD International Conference on Management of Data, Paris, France, June 13-18, 2004, pages 155–166.
ACM, 2004.
[9] G. Cormode and S. Muthukrishnan. An improved data stream summary: The count-min sketch and its applications. In Proceedings of LATIN, pages 29–38, 2004.
[10] Y. Gu, A. McCallum, and D. F. Towsley. Detecting anomalies in network traffic using maximum entropy estimation. In Proceedings of the 5th Internet Measurement Conference, IMC 2005, Berkeley, California, USA,
October 19-21, 2005, pages 345–350. USENIX Association, 2005.
21

[11] C. A. R. Hoare. Algorithm 65: Find. Commun. ACM, 4(7):321–322, July 1961.
[12] E. Liberty. Simple and deterministic matrix sketching. In Proceedings of KDD, pages 581–588, 2013.
[13] A. Manjhi, S. Nath, and P. B. Gibbons. Tributaries and deltas: Efficient and robust aggregation in sensor network
streams. In Proceedings of SIGMOD, pages 287–298, 2005.
[14] A. Manjhi, V. Shkapenyuk, K. Dhamdhere, and C. Olston. Finding (recently) frequent items in distributed data
streams. In Proceedings of ICDE, pages 767–778, 2005.
[15] G. S. Manku and R. Motwani. Approximate frequency counts over data streams. In Proceedings of VLDB,
pages 346–357. VLDB Endowment, 2002.
[16] A. Metwally, D. Agrawal, and A. El Abbadi. Efficient computation of frequent and top-k elements in data
streams. In Proceedings of ICDT, pages 398–412, 2005.
[17] J. Misra and D. Gries. Finding repeated elements. Science of Computer Programming, 2(2):143 – 152, 1982.
[18] M. Mitzenmacher, T. Steinke, and J. Thaler. Hierarchical heavy hitters with the space saving algorithm. In
Proceedings of ALENEX, pages 160–174, 2012.
[19] M. Mitzenmacher and E. Upfal. Probability and computing - randomized algorithms and probabilistic analysis.
Cambridge University Press, 2005.
[20] L. Rhodes, K. Lang, A. Saydakov, J. Thaler, E. Liberty, and J. Malkin. DataSketches: A Java software library of
stochastic streaming algorithms, 2017. https://datasketches.github.io.
[21] V. Sivaraman, S. Narayana, O. Rottenstreich, S. Muthukrishnan, and J. Rexford. Smoking out the heavy-hitter
flows with hashpipe. CoRR, abs/1611.04825, 2016. To appear in SDN 2017.
[22] A. Wagner and B. Plattner. Entropy based worm and anomaly detection in fast IP networks. In 14th IEEE
International Workshops on Enabling Technologies (WETICE 2005), 13-15 June 2005, Linköping, Sweden, pages
172–177. IEEE Computer Society, 2005.
[23] K. Xu, Z. Zhang, and S. Bhattacharyya. Profiling internet backbone traffic: behavior models and applications.
In R. Guérin, R. Govindan, and G. Minshall, editors, Proceedings of the ACM SIGCOMM 2005 Conference on
Applications, Technologies, Architectures, and Protocols for Computer Communications, Philadelphia, Pennsylvania, USA, August 22-26, 2005, pages 169–180. ACM, 2005.
[24] Y. Zhang, S. Singh, S. Sen, N. G. Duffield, and C. Lund. Online identification of hierarchical heavy hitters:
algorithms, evaluation, and applications. In A. Lombardo and J. F. Kurose, editors, Proceedings of the 4th ACM
SIGCOMM Internet Measurement Conference, IMC 2004, Taormina, Sicily, Italy, October 25-27, 2004, pages
101–114. ACM, 2004.

22

