Algorithms

Lecture 6: Filtering and Streaming [Sp’17]

Casus ubique valet; semper tibi pendeat hamus:
Quo minime credas gurgite, piscis erit.
[Luck affects everything. Let your hook always be cast.
Where you least expect it, there will be a fish.]— Publius Ovidius Naso [Ovid], Ars Amatoria, Book III (2 AD)
There is no sense being precise
when you don’t even know what you’re talking about.
— Attributed to John von Neumann

6

Filtering and Streaming

The randomized algorithms and data structures we have seen so far always produce the correct
answer but have a small probability of being slow. In this lecture, we will consider randomized
algorithms that are always fast, but return the wrong answer with some small probability.1 Moregenerally, we are interested in tradeoffs between the (likely) efficiency of the algorithm and the(likely) quality of its output.
Specifically, we introduce an error rate δ and analyze the running time required to guarantee
the output is correct with probability 1 − δ. For “high probability” correctness, we need δ < 1/ncfor some constant c. In practice, it may be sufficient (or even necessary) to set δ to a small
constant; for example, setting δ = 1/1000 means the algorithm produces correct results at least
99.9% of the time.

6.1

Bloom Filters

Bloom filters are a natural variant of hashing proposed by Burton Bloom in 1970 as a mechanism
for supporting membership queries in sets. In strict accordance with Stigler’s Law of Autonomy,
Bloom filters are identical to Zatocoding, a coding system for library cards developed by Calvin
Mooers in 1947. (Mooers was the person who coined the phrase “information retrieval”.)
A probabilistic analysis of Zatocoding appears in the personal notes of cybernetics pioneer W. Ross
Ashby from 1960.
A Bloom filter (or Zatocode) for a set X of n items from some universe U allows one to test
whether a given item x ∈ U is an element of X . Of course we can already do this with hash tablesin O(1) expected time, using O(n) space. Bloom (and Mooers) observed that by allowing false
positives—occasionally reporting x ∈ X when in fact x 6∈ X —we can still answer queries in O(1)expected time using considerably less space. False positives make Bloom filters unsuitable as anexact membership data structure, but because of their speed and low false positive rate, they arecommonly used as filters or sanity checks for more complex data structures.
A Bloom filter consists of an array B[0 .. m − 1] of bits, together with k hash functions
h1 , h2 , . . . , hk : U → {0, 1, . . . , m − 1}. For purposes of theoretical analysis, we assume the hashfunctions hi are mutually independent, ideal random functions. This assumption is of course
unsupportable in practice, but may be necessary to guarantee theoretical performance. Unlike
many other types of hashing, nobody knows whether the same theoretical guarantees can beachieved using practical hash functions with more limited independence.2 Fortunately, the actual
1Some textbooks (and Wikipedia) use the terms “Las Vegas” and “Monte Carlo” algorithms to respectively describe
these two types of randomized algorithms. Most algorithms researchers don’t.
2PhD thesis, anyone?
© Copyright 2018 Jeff Erickson.
This work is licensed under a Creative Commons License (http://creativecommons.org/licenses/by-nc-sa/4.0/).
Free distribution is strongly encouraged; commercial distribution is expressly forbidden.
See http://jeffe.cs.illinois.edu/teaching/algorithms/ for the most recent revision.

1

Algorithms

Lecture 6: Filtering and Streaming [Sp’17]

real-world behavior of Bloom filters appears to be consistent with this unrealistic theoreticalanalysis.
A Bloom filter for a set X = {x 1 , x 2 , . . . , x n } is initialized by setting the bit B[h j (x i )] to 1 for
all indices i and j. Because of collisions, some bits may be set more than once, but that’s fine.
MakeBloomFilter(X ):for h ← 0 to m − 1
B[h] ← 0for i ← 1 to nfor j ← 1 to k
B[h j (x i )] ← 1
return B

Given a new item y, the Bloom filter determines whether y ∈ X by checking each bit B[h j ( y)].
If any of those bits is 0, the Bloom filter correctly reports that y 6∈ X However, if all bits are 1, theBloom filter reports that y ∈ X , although this is not necessarily correct.
BloomMembership(B, y):for j ← 1 to k
if B[h j ( y)] = 0
return False
return Maybe

One nice feature of Bloom filters is that the various hash functions hi can be evaluated inparallel on a multicore machine.

6.2

False Positive Rate

Let’s estimate the probability of a false positive, as a function of the various parameters n, m,and k. For all indices h, i, and j, we have Pr[h j (x i ) = h] = 1/m, so ideal randomness gives usP r[B[h] = 0] =1 kn
1−≈ e−kn/mmfor every index h. Using this exact probability is rather unwieldy; to keep things sane, we will
use the close approximation p := e −kn/m instead.
The expected number of 0-bits in the Bloom filter is approximately mp; moreover, Chernoff
bounds imply that the number of 0-bits is close to mp with very high probability. Thus, theprobabililty of a false positive is very close3 to(1 − p)k = (1 − e−kn/m )k .
If all other parameters are held constant, then the false positive rate increases with n (the numberof items) and decreases with m (the number of bits). The dependence on k (the number of hashfunctions) is a bit more complicated, but we can derive the best value of k for given n and m asfollows. Consider the logarithm of the false-positive rate:mln (1 − p)k = k ln(1 − p) = − ln p ln(1 − p).
nBy symmetry, this expression is minimized when p = 1/2. We conclude that, the optimal
number of hash functions is k = ln 2 · (m/n), which would give us the false positive rate3This analysis, originally due to Bloom, assumes that certain events are independent even though they are not; asa result, the estimate given here is slightly below the true false positive rate.

2

Algorithms

Lecture 6: Filtering and Streaming [Sp’17](1/2)ln 2(m/n) ≈ (0.61850)m/n . Of course, in practice, k must be an integer, so we cannot achieveprecisely this rate, but we can get reasonably close (at least if m  n).
Finally, the previous analysis implies that we can achieve any desired false positive rate δ > 0using a Bloom filter of size¡¤lg(1/δ)m=n = Θ(n log(1/δ))ln 2that uses with k = dlg(1/δ)e hash functions. For example, we can achieve a 1% false-positive rateusing a Bloom filter of size 10n bits with 7 hash functions; in practice, this is considerably fewer
bits than we would need to store all the elements of S explicitly. With a 32n-bit table (equivalent
to one integer per item) and 22 hash functions, we get a false positive rate of just over 2 · 10−7 .

ÆÆÆDeletions via counting filters? Key-value pairs via Bloomier filters? Other extensions?

6.3

Streaming Algorithms

A data stream is an extremely long sequence S of items from some universe U that can be read
only once, in order. Good examples of data streams include the sequence of packets that passthrough a network router, the sequence of searches at google.com, the sequence of all bids on theNew York Stock Exchange, and the sequence of humans passing through the Shinjuku Railway
Station in Tokyo. Standard algorithms are not appropriate for data streams; there is simply too
much data to store, and it arrives too quickly for any complex computations.
A streaming algorithm processes each item in a data stream stream as it arrives, maintainingsome summary information in a local data structure. The basic structure of every streaming
algorithm is the following:
DoSomething(S):〈〈initialize〉〉
while S is not donex ← next item in S〈〈do something fast with x〉〉
return 〈〈something〉〉

Ideally, neither the running time per item nor the space used by the data structure depends
on the overall length of the stream; viewed as algorithms in the traditional sense, all streaming
algorithms run in constant time! Somewhat surprisingly, even within this very restricted model,
it is possible to compute interesting properties of the stream using randomization, provided weare willing to tolerate some errors in the output.

6.4

The Count-Min Sketch

As an example, consider the following problem: At any point during the stream, we want toestimate the number of times that an arbitrary item x ∈ U has appeared in the stream so far.
This problem can be solved with a variant of Bloom filters called the count-min sketch, firstpublished by Graham Cormode and S. Muthu Muthukrishnan in 2005.
The count-min sketch consists of a w × d array of counters (all initially zero) and d hashfunctions h1 , h2 , . . . , hd : U → [m], drawn independently and uniformly at random from a2-uniform family of hash functions. Each time an item x arrives in the stream, we call
CMIncrement(x). Whenever we want to estimate the number of occurrences of an item x sofar, we call CMEstimate(x).
3Algorithms

Lecture 6: Filtering and Streaming [Sp’17]

CMEstimate(x):est ← ∞for i ← 1 to dj ← hi (x) est ← min est, Count[i, j]
return est

CMIncrement(x):for i ← 1 to dj ← hi (x)Count[i, j] ← Count[i, j] + 1

If we set w := de/"e and d := dln(1/δ)e, then the data structure uses O( 1" log δ1 ) space andprocesses updates and queries in O(log δ1 ) time.
Let f x be the true frequency (number of occurrences) of x, and let fˆx be the value returned
by CMEstimate. It is easy to see that f x ≤ fˆx ; we can never return a value smaller than theactual number of occurrences of x. We claim that Pr[ fˆx > f x + "N] < δ, where N is the total
length of the stream. In other words, our estimate is never too small, and with high probability,
it isn’t a significant overestimate either. (Notice that the error here is additive; the estimates or
truly infrequent items may be much larger than their true frequencies.)
For any items x 6= y and any index j, we define an indicator variable X i,x ,y = [hi (x ) = hi (y)];because the hash functions hi are universal, we haveE[X i,x, y ] = Pr[hi (x) = hi ( y)] =1.
w

PLet X i,x := y6= x X i,x ,y · f y denote the total number of collisions with x in row i of the table.
Then we immediately haveCount[i, hi (x)] = f x + X i,x ≥ f x .
On the other hand, linearity of expectation implies
E[X i,x ] =X

E[X i,x, y ] · f y =y6= x

1 XN.
fy ≤w y6= xw

Now Markov’s inequality implies
Pr[ fˆx > f x + "N ] = Pr[X i,x > "N for all i]d= Pr[X 1,x > "N ]
E[X 1,x ] d≤"N dN /w d1≤="Nw"[definition][independence of hi ’s][Markov’s inequality][derived earlier]

Now setting w = de/"e and d = dln(1/δ)e gives us Pr[â x > a x + "N ] ≤ (1/e)ln(1/δ) = δ, asclaimed.

6.5

ÆÆÆEstimating Distinct Items
Write this, possibly as a simpler replacement for the count-min sketch. AMS estimator:

2z+1/2 where z = max{zeros(x) | x ∈ S}? Or stick with the Flajolet-Martin/Bar-Yossef-et-al
estimator in the exercises? Median amplification.
Estimating larger moments?

4

Algorithms

Lecture 6: Filtering and Streaming [Sp’17]

Exercises
1. Reservoir sampling is a method for choosing an item uniformly at random from anarbitrarily long stream of data; for example, the sequence of packets that pass through arouter, or the sequence of IP addresses that access a given web page. Like all data streamalgorithms, this algorithm must process each item in the stream quickly, using very littlememory.
GetOneSample(stream S):`←0
while S is not donex ← next item in S`←`+1
if Random(`) = 1sample ← x(?)
return sample

At the end of the algorithm, the variable ` stores the length of the input stream S; thisnumber is not known to the algorithm in advance. If S is empty, the output of the algorithmis (correctly!) undefined. In the following, consider an arbitrary non-empty input stream S,
and let n denote the (unknown) length of S.
(a) Prove that the item returned by GetOneSample(S) is chosen uniformly at random
from S.
(b) What is the exact expected number of times that GetOneSample(S) executes line (?)?
(c) What is the exact expected value of ` when GetOneSample(S) executes line (?) forthe last time?
(d) What is the exact expected value of ` when either GetOneSample(S) executes line (?)
for the second time (or the algorithm ends, whichever happens first)?
(e) Describe and analyze an algorithm that returns a subset of k distinct items chosen
uniformly at random from a data stream of length at least k. The integer k is given as
part of the input to your algorithm. Prove that your algorithm is correct.
For example, if k = 2 and the stream contains the sequence 〈«, ª, ©, ¨〉, thealgorithm should return the subset {©, «} with probability 1/6.

2. In this problem, we will derive a simple streaming algorithm (first published by Ziv
Bar-Yossef, T. S. Jayram, Ravi Kumar, D. Sivakumar, and Luca Trevisan in 2002) to estimate
the number of distinct items in a data stream S.
Suppose S contains n unique items (but possibly several copies of each item); as usual,the algorithm does not know n in advance. Given an accuracy parameter 0 < " < 1 and aconfidence parameter 0 < δ < 1 as part of the input, our final algorithm will compute ane such that Pr[|Ne − n| > "n] < δ.
estimate N
As a first step, fix a positive integer m that is large enough that we don’t have toworry about round-off errors in the analysis. Our first algorithm chooses a hash function
h: U → [m] at random from a 2-uniform family, computes the minimum hash valuee = m/ħħh = min{h(x) | x ∈ S}, and finally returns the estimate nh.
5

Algorithms

Lecture 6: Filtering and Streaming [Sp’17](a) Prove that Pr [en > (1 + ")n] ≤ 1/(1 + ").
(b) Prove that Pr [en < (1 − ")n] ≤ 1 − ".

[Hint: Markov’s inequality][Hint: Chebyshev’s inequality](c) We can improve this estimator by maintaining the k smallest hash values, for someek = k·m/ħ
integer k > 1. Let n
hk , where ħhk is the kth smallest element of {h(x) | x ∈ S}.
Estimate the smallest value of k (as a function of the accuracy parameter ") suchthat Pr[|enk − n| > "n] ≤ 1/4.
(d) Now suppose we run d copies of the previous estimator in parallel to generate dek,1 , nek,2 , . . . , nek,d , for some integer d > 1. Each copy uses its
independent estimates n
own independently chosen hash function, but they all use the same value of k thate be the median of these d estimates.
you derived in part (c). Let N
Estimate the smallest value of d (as a function of the confidence parameter δ)
e − n| > "n] ≤ δ.
such that Pr[|N© Copyright 2018 Jeff Erickson.
This work is licensed under a Creative Commons License (http://creativecommons.org/licenses/by-nc-sa/4.0/).
Free distribution is strongly encouraged; commercial distribution is expressly forbidden.
See http://jeffe.cs.illinois.edu/teaching/algorithms/ for the most recent revision.

6