Bloom Filters and Count-Min Sketch

Two algorithms sit at the heart of windowed stream analytics. A Bloom filter answers one question about an element: is it a member of the current window or not? A count-min sketch answers a different one: how many times has it appeared? Both trade a small amount of error for a huge saving in memory, and both matter for the exam. This session works through both from first principles — the bit-sequence idea behind the Bloom filter, the collision problem, the false positive analysis with its full derivation, a worked problem in the style of an exam question, and then the row-and-column mechanics of the count-min sketch.

The stakes are practical. A window can hold on the order of 10^6 to 10^7 events, and keeping an exact set or an exact per-key count at that scale costs memory that streaming servers cannot spare. The two structures in this session answer the two questions stream analytics actually asks — "has this arrived before?" and "how often does this arrive?" — with a few million bits and a small table of counters, in exchange for an error you can size and control. By the end you should be able to compute that error by hand, which is exactly what the exam asks for.

Roadmap. Section 14.1 builds the Bloom filter: the bit-sequence idea, hashing, collisions, the multi-hash design, the false positive formula and its derivation, the optimal number of hash functions, and a four-part worked problem. Section 14.2 builds the count-min sketch: the counter table, the insertion rule, and the minimum-at-query-time rule. Two appendices close with exam guidance and industry applications.

14.1 Bloom Filter

14.1.1 The Core Idea: A Bit Sequence Instead of a Boolean Array

A Bloom filter is a membership technique: you filter events based on a particular strategy. Filtering here is just applying an if statement — if the element is in the filter, let it through; otherwise drop it. The version studied here lives inside a window, so the question it answers is whether a particular element is a member of the window filter or not: "we will put a question whether a particular element is a member of this filter or not member of our window filter, means window, because we work with windows."

The starting point is storing items as a bit sequence instead of a regular array. Suppose the elements are 1, 5, 6, 9, 11, 21, 30, and we use a single int variable x. One int takes 4 bytes; one byte is 8 bits; so x holds 32 bits. Index those 32 bits from 1 to 32: bit 1, bit 2, and so on up to bit 30, bit 31. Wherever a number appears in our set, set that bit to 1; everywhere else the bit stays 0.

The natural objection: what if an element is bigger than 30, say 60? With this direct notation the set cannot be represented at all. The answer is hashing — you map the value into the 1-to-32 range, which is what Section 14.1.2 does.

A student then checked the memory side of the design: instead of creating an array for all those elements, could we use just four bytes of memory with a Boolean bit sequence?

One more clarification matters before moving on: the filter does not count occurrences.

The direct idea is deliberately naive: 32 positions, 32 bits. The rest of the lecture fixes its two limits — range (hashing) and collisions — while keeping the core bargain: bits are cheap, memory stays fixed, and the error stays controllable.

14.1.2 Hashing: Mapping Any Key into the Filter

The direct bit-position trick only works for keys that are small integers. Real keys — event IDs, strings, arbitrary values — can be anything. So the filter never stores the key itself: we hash the key, see which location it lands on, and store a 1 there.

A hash function (a deterministic rule that squeezes an arbitrary key down to one number in a fixed range), written h, maps any key k into the range 1 to m, where m is the filter size. The same key always produces the same output — that is what makes the method reproducible: insert by computing h(k) once, and the membership test later recomputes exactly the same value. To insert a key k, compute h(k) and set bit h(k) to 1. The membership test is the same operation: compute h(k), look at that bit, and report "present" if it is 1.

A student's worry about the range was addressed directly: "we have cells between 1 to 32, but your keys need not be these integer representations. That is the reason we are using hashing, where the hash value will be between 1 to 32 — that is the idea." The exact bound is not sacred; the logic is that the hash maps any key into the filter's range. Values such as 60 are handled the same way, and zero is not a special case — the value only needs to land inside the range.

One more property drives everything that follows: the hash must spread keys evenly across the positions. In production, streaming systems use fast, non-cryptographic hashes (such as MurmurHash) precisely because they scatter keys well and cost little per key — a necessity at millions of events per window. A weak hash that funnels many keys onto few positions is the direct cause of the problem in the next subsection.

14.1.3 Collisions Cause False Positives

A single hash function has a flaw: two different keys can hash to the same location. That is a collision, and it breaks membership reporting.

That wrong answer has a name. A false positive (the filter reports that an element is present when it is not) is the error this algorithm trades for memory. Its source is the collision: "due to collision, the filter returns incorrectly the presence of the element. That means even the element is not there, it will show that the element is present."

Notice the direction of the error. Bits only ever go from 0 to 1 — insertion never clears a bit. So the filter can never say "absent" for something that really was inserted: false negatives are impossible. Every error the filter can make is a false positive, and that one-way property is what makes the design safe to use — a wrong "yes" can be re-checked later, while a wrong "no" could drop an event forever.

A student proposed eliminating collisions altogether: use a mod function that uniquely generates a unique hash value for every unique number. The instructor rejected that direction:

14.1.4 Multiple Hash Functions and the Mask Check

Use k hash functions; the lecture standard is three. To insert a key x, set bits h1(x), h2(x), and h3(x). To test membership, compute all three values — i1 = h1(x), i2 = h2(x), i3 = h3(x) — and report "present" only if all three bits are 1 at the same time.

Why three instead of one? For a false positive now, every hash function would have to collide simultaneously, and with a large filter that is very unlikely: "when simultaneously they are satisfying this, I will say yes, because simultaneously it is very less likely that every hash function will face this problem, if my filter is very large."

The practical check uses a mask. Build a second bit array with zeros everywhere except the three positions i1, i2, i3, where the mask has 1s. Then AND the filter with the mask. If the AND result is 1 — meaning those three locations were already 1 in the filter — the element is present. All other positions are masked out, so they never matter for this query: "I put everywhere zero except these three positions... when I do the AND operator, if my AND operator is returning 1, definitely only these three locations, anyway it is present — I don't bother about other locations."

The mask is a single cheap bitwise operation per query: one AND of two m-bit arrays. That is the whole cost of membership — two memory reads and one AND — which is why the filter can keep up with millions of events per window.

There is no foolproof design. At event scales of 10^6 or 10^7 per window, collisions cannot be eliminated, so the design goal becomes explicit: how do we design a filter that reduces the false positive rate? That is the problem statement the whole analysis in the next sections solves.

Real-world: this is the motivation behind every approximate membership structure in stream platforms — at 10^6 to 10^7 events per window you cannot keep a set of every key, so you pay a controlled false positive rate to get a filter of a few million bits. In online advertising, for example, ad networks keep Bloom filters of seen click and impression IDs to throw away duplicate clicks before they reach billing and bidding systems — they accept a small false positive rate because dropping a few valid events is cheaper than counting fake ones.

14.1.5 False Positive Analysis: The Probability Chain

Three parameters control the filter:

• k — the number of hash functions used in the filter design.
• m — the filter size: the number of positions (bits) the filter can hold.
• n — the occupancy: how many elements are currently stored in the filter right now (not its maximum capacity).

The false positive rate is a probability question, and the lecture builds it as a chain: first one bit and one insertion, then more hash functions, then more insertions. Every step tracks the probability of the bit staying 0, because a false positive is exactly a bit being 1 when it should not be.

Start with a single bit and a single insertion. With one hash function h1, the bit becomes 1 if h1(x) lands on it, which happens with probability 1/m — a uniform hash visits each of the m positions with equal chance. So the probability that the bit is still 0 after one insertion using h1 is:

$$P(\text{bit is 0 after one insertion, one hash function})=1-\frac{1}{m}$$

"Because when you use one hash function, it can occupy any one of the slots of the m."

Now add a second hash function h2. The bit survives if it escapes h1 AND h2. Because the hash functions are independent, the probabilities multiply — the AND of two independent events multiplies their probabilities:

$$P(\text{bit is 0 after one insertion, two hash functions})={\left(1-\frac{1}{m}\right)}^2$$

Generalizing to all k hash functions, for one insertion:

$$P(\text{bit is 0 after one insertion, all }k\text{ hash functions})={\left(1-\frac{1}{m}\right)}^k$$

That was one insertion. After n insertions we repeat the process n times — each insertion is an independent throw of k darts at the m bits — so the survival probability multiplies n times again:

$$P(\text{bit is still 0 after }n\text{ insertions})={\left(1-\frac{1}{m}\right)}^{nk}$$

A false positive happens exactly when the bit a queried key's hash points to is 1 even though the key was never inserted — a bit that is 1 incorrectly. The probability of incorrectly reporting presence for one hash function is one minus the probability the bit is still 0, and the same condition must hold for all k hash functions at once. The total false positive rate is:

$$\text{FPR}={\left(1-{\left(1-\frac{1}{m}\right)}^{nk}\right)}^k$$

The verbal description that produced it: "the total false positive rate is nothing but one minus of one minus 1 by m, power nk, whole to the power of k, because this is the false positive rate due to all k hash functions."

Two quick reality checks on the formula before continuing. With nothing inserted (n = 0), the inner bracket becomes $1-1^0=0$, so FPR = 0 — an empty filter never lies. And as the filter grows (m → ∞), $(1-1/m{)}^{nk}$ approaches 1, the inner bracket approaches 0, and FPR approaches 0 — an enormous filter never collides. Both limits behave as they must, which confirms the shape of the derivation. (The independence of the hash functions, and of the insertions, are the assumptions quietly baked into every multiplication.)

14.1.6 Approximating the False Positive Rate

The exact form $(1-1/m{)}^{nk}$ is awkward to work with, so the lecture approximates it using the binomial expansion. Recall the binomial theorem for $(1+x{)}^m$: it expands as 1 + C(m,1)x + C(m,2)x^2 + ... + C(m,m)x^m, that is:

$$(1+x{)}^m=\sum _{i=0}^m(\genfrac{}{}{0ex}{}{m}{i})x^i$$

Apply the same pattern to our term, with x = −1/m and the exponent nk:

$${\left(1-\frac{1}{m}\right)}^{nk}=\sum _{r=0}^{nk}\left(\genfrac{}{}{0ex}{}{nk}{r}\right){\left(-\frac{1}{m}\right)}^r$$

where the binomial coefficient is:

$$\left(\genfrac{}{}{0ex}{}{nk}{r}\right)=\frac{nk(nk-1)(nk-2)\cdots (nk-r+1)}{r!}$$

Because nk is very large, subtracting 1, 2, and so on barely matters, so C(nk, r) is about (nk)^r / r!. And because nk is so large, the sum may be extended to infinity — the terms beyond r = nk are all negligible:

$${\left(1-\frac{1}{m}\right)}^{nk}\approx \sum _{r=0}^{\infty }\frac{(-nk/m{)}^r}{r!}=e^{-nk/m}$$

The infinite sum on the right is exactly the exponential series — this is where the e in the formula comes from. Substituting back into the false positive rate:

$$\text{FPR}\approx {\left(1-e^{-nk/m}\right)}^k$$

The instructor paused after this step so everyone could copy the derivation down, and repeated the outcome.

14.1.7 The Optimal Number of Hash Functions and Load Factor

Given m and n, how many hash functions should we use? The optimal k is found by setting:

$$e^{-nk/m}=\frac{1}{2}$$

The intuition: a well-designed filter leaves its bits as uncertain as possible — probability 1/2 of being 0 and 1/2 of being 1. A bit that is almost always 0 is doing no work: it never flips for a queried key, so its position never contributes a false positive — but it also means the filter is far larger than needed. A bit that is almost always 1 makes every query hit a wall of 1s, and false positives multiply. The halfway point — each bit a fair coin flip — is the design sweet spot: "The total probability of identifying a bit is 0 or a bit is 1 is 1/2, 1/2. When I say 1 minus this quantity, you can set this quantity to 1/2. That can be your k optimal."

Take the natural log of both sides:

$$\ln \left(e^{-n{k}_{\text{opt}}/m}\right)=\ln \left(\frac{1}{2}\right)\Rightarrow -\frac{n{k}_{\text{opt}}}{m}=-\ln 2$$

The log of the exponential cancels the base: $\ln (e^a)=a$ on the left, and $\ln (1/2)=-\ln 2$ on the right. Multiply both sides by −m/n:

$$k_{\text{opt}}=\frac{m}{n}\ln 2$$

The instructor quoted ln 2 as about 0.691 (the true value is 0.6931), giving the memorable forms:

$$k_{\text{opt}}=0.691\cdot \frac{m}{n}=\frac{0.691}{\alpha }$$

where α = n/m is the load factor of the filter — the fraction of the filter that is filled, the percentage of occupancy. (The same answer falls out of minimizing the approximate FPR with respect to k by calculus; the professor's half-and-half argument reaches it without any derivatives.)

The same rule is often quoted as a bits-per-element figure: budget c bits per element, use about k = c·ln 2 hash functions, and the expected false positive rate lands near $0.6185^c$. Eight bits per element, for example, gives about 6 hash functions and a false positive rate near 2% — a standard sizing rule used before deploying a filter.

14.1.8 Worked Problem: False Positive Rate for a 6 MB Filter

The instructor solved the following problem in full, saying the class should know how exam questions will come — "we should know how exam questions will come, that's why I'm showing this." The problem below is the one worked in class: its exact slide wording was partly garbled in the source material, so the four parts (a)–(d) follow the in-class discussion, which was complete.

A Bloom filter with capacity 6 MB stores 10^6 events using 3 hash functions.

Part (c) — what conclusion can be drawn from (a) and (b)? The conclusion is that increasing the filter capacity further reduces the false positive rate. More bits, fewer collisions, smaller error.

Real-world: this is the sizing trade-off behind every approximate filter deployment — memory budget versus accuracy. The same formula is what you use to pick a filter size before you deploy, and the 6 MB-to-60 MB comparison is the textbook form of that decision. Production figures land on the same curve: about 9.6 bits per element buy a 1% false positive rate, and under 1 MB tracks a million domain names at under 2.5% error.

14.1.9 Worked Problem: Part D — The Optimal Hash Count and Its Disadvantage

Part (d) of the problem asked about the number of hash functions. Using the optimal count formula:

$$k_{\text{opt}}=\frac{m}{n}\ln 2=\frac{48\times 10^6}{10^6}\times \ln 2=48\times \ln 2\approx 48\times 0.693\approx 33.27$$

(The instructor read the result as "around 33.27"; using the rounded constant 0.691 instead of 0.693 gives about 33.17 — the difference is a rounding artifact, not a conceptual one.)

So the formula nominally says: use about 33 hash functions. The obvious trap is to take that number at face value. Thirty-three hash functions means computing 33 hashes for every event, every insertion, every query. The computation is very high, and the performance of the filter deteriorates badly.

The general decision rule the instructor stated: before deciding to increase the number of hash functions, always look at your current false positive rate, and ask whether the increase is worth its computational cost. If the rate is already below 1%, adding hash functions usually buys nothing.

One last shortcut students often puzzle over:

14.2 Count-Min Sketch

14.2.1 The Sketch Table and the Insertion Rule

Where the Bloom filter answers "present or not?", the count-min sketch answers "how many times?" It estimates frequency: the number of times a particular element has occurred in the stream — "count-min sketch is frequency, that means number of times a particular element present in the filter."

The data structure is a small table called the sketch table. Like every table it has rows and columns; in the lecture example, 3 columns and 4 rows. The columns are the hash functions — one per column — and the rows are the possible hash values, 1 through 4. The cell A_ij holds a counter. (Notation: texts call the number of columns the depth of the sketch and the number of rows the width; the lecture just calls them columns and rows.)

The insertion rule is one line. If the j-th hash function maps key K to row i, written Hj(K) = i, then we increment the counter in cell A_ij: "if I say Hj of my K is equal to i, that means matrix element Aij... it indicates that we should increment the counters."

So the procedure for one arriving event is: for each hash function j = 1, 2, 3, compute the row i = Hj(K), and add 1 to the counter in cell (i, j). Nothing else happens at insert time — no comparisons and no bookkeeping of the key itself.

14.2.2 Worked Insertions: Three Keys, Three Rows of Counters

Now "History of Japan" appears again — a third insertion. It hashes to the same places as before: (1,1), (2,2), and (1,3). Cell (1,1) goes 2 → 3, cell (2,2) goes 1 → 2, cell (1,3) goes 1 → 2.

After three insertions the table reads:

Or, drawn as the full 4-row by 3-column grid (rows are hash values 1–4, columns are hash functions H1–H3):

The pattern to notice: a key that appears multiple times keeps hitting the same cells, so its cells accumulate the largest counts. But other keys also touch those cells — (1,1), for example, was bumped by both "History of Japan" and "European history" — which is exactly the pollution the query rule below defends against. Notice also that no cell's value equals a single key's count: (1,1) holds 3, yet no key appears three times in the stream.

Real-world: this is how streaming systems estimate heavy hitters and top-k style aggregates without storing the event stream — every event touches only a handful of counters. In production, the counter table is usually paired with a small heap of candidate keys, so the system can report "the 10 most frequent keys" on demand.

14.2.3 Querying Frequency: Take the Minimum

To find the frequency of a key, hash it with all three hash functions, read the three cells the hashes point to, and report the minimum of the three counters.

Check the same procedure against the two inserted keys: "History of Japan" reads (3, 2, 2) → minimum 2, its true count; "European history" reads (2, 1, 1) → minimum 1, its true count. The method gives exact answers for the keys that were inserted, and a wrong-but-nonzero guess (1 instead of 0) for the never-inserted "hello".

That reasoning gives the sketch's core guarantee: the answer never underestimates the true count — every reading is the true count plus some non-negative collision noise, so the minimum is noise-resistant by construction. With a wide enough table and enough rows the overestimate stays small; the original paper shows the estimate stays within a small error of the true count with high probability when the width and depth are chosen properly.

The two structures answer the two questions, and the exam asks you to keep them apart:

One-sentence rule: use the Bloom filter when the window question is about membership, and the count-min sketch when it is about frequency — and remember which error each one can make.

Exam Guidance Summary

• The false positive formula is the headline. FPR = (1 − e^{−nk/m})^k is "very, very important" from the exam point of view — note it down and be ready to substitute numbers into it. Know what each parameter means: m is the filter size in bits, n is the occupancy (elements currently in the filter), k is the number of hash functions.
• The derivation is process material. The probability chain, then the binomial expansion to the exponential, is not asked as a proof in the exam, but you should remember how the process runs — the proof matters because problems may be built on it. A OneNote containing the step-by-step derivation of the Bloom filter formula was shared for revision, and a review session follows this one.
• Expect four-part worked problems. Worked problems of the kind solved here — capacity in MB, events count, hash count, parts (a) through (d) — show how exam questions come. Expect to compute a false positive rate, compare capacities, state a conclusion, and discuss the number of hash functions.
• Use the 1024 ≈ 1000 convention. In all calculations, assume 1024 ≈ 1000 (10^3): 6 MB becomes 6 × 10^6 bytes, then 48 × 10^6 bits at 8 bits per byte.
• Optimal hash count: k_opt = (m/n) ln 2 = 0.691/α, with α = n/m the load factor. A 70% loaded filter needs about 1 hash function. If the current false positive rate is already below 1%, adding hash functions usually buys nothing.
• Do not confuse the two structures. The Bloom filter answers presence; the count-min sketch answers frequency. Each has its own query rule: all-k-bits for the filter, minimum of the cells for the sketch.
• Count-min sketch hashes are given. Hash values are given in the problem and are not computed in the exam unless the question specifies how to compute them.
• Revision focus: the Bloom filter, the count-min sketch, and the decaying window algorithm (covered previously) are the important algorithms; also go through the lecture notes and structured streaming.

Key Industry Applications

• Membership and frequency at stream scale. Membership filtering and frequency counting at event scales of 10^6 to 10^7 per window are exactly the workloads stream-processing platforms handle; the Bloom filter and count-min sketch are the memory-efficient answers. Every event touches only a handful of bits or counters, which is the only way a server can keep up with millions of events per minute.
• Sizing decisions in production. The false positive formula drives deployment sizing — the 6 MB versus 60 MB comparison in the worked problem is the same memory-versus-accuracy trade-off made in production. Online advertising is a live example: networks keep Bloom filters of seen click and impression IDs to drop duplicate clicks before billing and bidding, accepting a small false positive rate because a few lost valid events cost less than counting fake ones.
• Frequency estimation without storing the stream. The count-min sketch's counter-table design is how stream systems estimate frequencies and heavy hitters without keeping the full event stream, touching only a few counters per event. Pairing the table with a small heap of candidate keys turns it into a top-K or heavy-hitters engine — the standard way streaming platforms surface the most frequent items in a window.