Count-min sketch and HyperLogLog

A count-min sketch and HyperLogLog are small, fixed-size summaries of a stream that answer counting questions approximately. A count-min sketch estimates how many times an item has appeared, and can only overcount. HyperLogLog estimates how many distinct items there are; Redis does it in 12 KB with about 0.81% standard error. Both merge across servers and time windows, which is why analytics, trending and monitoring pipelines are built on them.

Picture it first: number plates and tally sheets

How many different autos passed the junction today? You stand at a busy junction with no notebook big enough for every number plate, and many autos pass more than once. So you remember just one thing: the most trailing zeros you have seen on any plate. Plate numbers are effectively random, so about 1 in 10 ends in 0, 1 in 100 in 00, and 1 in 1,000 in 000. If your record at sunset is 000, you probably saw something like a thousand different autos. An auto that passes ten times shows the same plate ten times and can’t move the record, so repeats are ignored for free.

One record is noisy: a lucky 000 in the first minute would fool you. So you keep ten records instead, one for each first digit of the plate, and average them. That is HyperLogLog: hash each item, remember the rarest pattern per bucket, and average across buckets.

How many times did each customer buy? A busy shop has no room for a page per customer. Instead it keeps three tally sheets of ten columns each, and three different rules map a customer’s name to one column on each sheet. Every purchase adds a tally mark in that customer’s column on all three sheets. To ask how often Ravi bought, look at his three columns and take the smallest. Other customers share those columns, so each column can only be too high, never too low, and the smallest is the one least polluted by strangers. That is a count-min sketch.

Map it back: plates and names are hashed items; the records and tally columns are registers and counters; and because the number of sheets and records is fixed, memory never grows with the stream.

Why exact counting gets expensive

Take a food-delivery app that logs 500 million events a day (app opens, searches, orders) from up to 100 million distinct users. Two everyday questions:

• How many distinct users today? To answer exactly, you must remember every user ID you have seen. In a Redis set, at about 24 bytes of overhead plus 8 bytes per ID, that is 100M × 32 B = 3.2 GB for one number. Ask it per city (500 cities) and per hour, and you need a set per combination; and getting “daily users in Mumbai” from 24 hourly sets means unioning them, re-reading every ID.
• How often was each search term used? Exactly, that needs a counter per distinct term. With 50 million distinct terms at a lean 50 bytes each (the string, a counter and hash-table pointers), that is 50M × 50 B = 2.5 GB per day, per region.

A sketch replaces the exact structure with a fixed-size summary. You gain three things: memory that doesn’t grow with the data (kilobytes to a few megabytes), constant-time updates, and mergeability, meaning sketches from different servers or time windows combine into the sketch of the combined data without re-reading anything. You pay with a bounded, known error, and you lose the ability to list the items you counted.

Count-min sketch: counting with collisions

Graham Cormode and S. Muthukrishnan published the count-min sketch in 2005. It answers point queries (“how many times has x appeared?”) over a stream of updates, using memory that depends only on the accuracy you ask for.

Update and query

A count-min sketch is a table of d rows × w counters, all starting at zero, plus d independent hash functions, one per row, each mapping an item to a column from 0 to w − 1.

• Update(x, c): in every row j, add c to the counter in column h_j(x). That is one counter per row, d in total.
• Query(x): read the same d counters and return the minimum.

Why the minimum? Each counter x touches holds x’s true count plus whatever other items collided into it. As long as counts only go up, collisions can only add, so every one of the d counters is at least the true count, and the smallest is the best estimate. A count-min sketch never undercounts. It overcounts only when every row has a collision, as #dosa does in the figure.

Error bounds and sizing

Let N be the total of all updates (the stream length, when each event adds 1). Cormode and Muthukrishnan prove that if you choose

w = ⌈e / ε⌉        where e ≈ 2.718
d = ⌈ln(1/δ)⌉

then every estimate satisfies true ≤ estimate ≤ true + ε·N with probability at least 1 − δ. The intuition: each row spreads the whole stream over w counters, so the expected collision noise in any one counter is at most N/w = ε·N/e. By Markov’s inequality, the chance that a row’s noise exceeds ε·N is at most 1/e, and the estimate is only that bad if all d independent rows are, which happens with probability (1/e)^d = δ.

Worked example. A search service sees N = 1 billion queries a day and wants errors of at most 0.01% of traffic (ε = 0.0001) with 99.9% confidence (δ = 0.001):

• w = ⌈2.718 / 0.0001⌉ = 27,183 counters per row.
• d = ⌈ln 1000⌉ = ⌈6.91⌉ = 7 rows.
• 27,183 × 7 = 190,281 counters; at 4 bytes each that is about 760 KB, against roughly 2.5 GB for exact counts.

Each estimate is then at most 0.0001 × 1e9 = 100,000 too high, with probability 99.9%. For a query searched 5 million times that is at most 2% off. For one searched 300 times, the sketch might report anything up to 100,300; it simply can’t resolve rare items. The error is a fraction of the whole stream, not of the item, which makes a count-min sketch a tool for frequent items.

Two sizing rules fall out. Width follows 1/ε, so halving the error doubles the memory. Depth follows ln(1/δ), so each extra “9” of confidence costs only about 2.3 more rows (ln 10 ≈ 2.3).

Conservative update

A plain update adds c to all d counters, although only the smallest one matters for x. Conservative update, from Cristian Estan and George Varghese’s 2002 work on traffic measurement, raises each of x’s counters only as far as needed: compute the current estimate (the minimum), then set each counter to max(counter, estimate + c). Counters that were already higher because of collisions are left alone, so less noise leaks into other items. In their measurements on real traffic traces, conservative update (together with one other optimisation) improved accuracy by about an order of magnitude.

The cost: it only works when counts never decrease, and sketches built this way are no longer simple sums of their inputs. Adding two of them together still never undercounts, but loses some of the gain.

Heavy hitters and top-k

A count-min sketch tells you how often x appeared, but it stores no item names, so it can’t tell you which items are frequent. Add a small candidate set, usually a min-heap of size k:

1. On each event, update the sketch and read back the item’s estimate.
2. If the item is already a candidate, refresh its estimate. Otherwise, if there is room or its estimate beats the smallest candidate, add it and evict the smallest.
3. At the end of the window, the candidates are the top k by estimated count.

This is essentially the heavy-hitters procedure in the original paper. Because the sketch never underestimates, a truly heavy item is never missed; items just below the cut-off may sneak in.

import hashlib

class CountMin:
    def __init__(self, width, depth):
        self.w, self.d = width, depth
        self.rows = [[0] * width for _ in range(depth)]

    def _cols(self, key):
        h = hashlib.blake2b(key.encode(), digest_size=16).digest()
        h1, h2 = int.from_bytes(h[:8], "little"), int.from_bytes(h[8:], "little")
        return [(h1 + i * h2) % self.w for i in range(self.d)]

    def add(self, key, c=1):
        for row, col in zip(self.rows, self._cols(key)):
            row[col] += c

    def estimate(self, key):
        return min(row[col] for row, col in zip(self.rows, self._cols(key)))

def top_k(stream, k, cms):
    best = {}                                # candidate -> latest estimate
    for key in stream:
        cms.add(key)
        best[key] = cms.estimate(key)
        if len(best) > k:
            del best[min(best, key=best.get)]
    return sorted(best.items(), key=lambda kv: -kv[1])

The row hashes reuse the two-hash trick from Bloom filters. In a test with 500,000 hashtag events drawn from 100,000 tags with a skewed (Zipf-like) popularity, a 2,719 × 7 sketch (ε ≈ 0.1%) returned the same top 10, in the same order, as an exact count, with every estimate within 47 of the truth against a guaranteed bound of 0.001 × 500,000 = 500.

At scale: shards and sliding windows

Two properties make this work across machines:

• Linearity. Sketches with the same w, d and hash functions add cell by cell, and the sum is exactly the sketch of the combined stream. Shards build their own and a merger sums them; Redis exposes this as CMS.MERGE.
• Windows. Keep one sketch per minute. An hour is the sum of the last 60, and as the window slides you add the newest minute and subtract the one that expired. (Subtraction is safe for plain updates, not for conservative ones.)

The trap is the candidate list. A hashtag that is moderately popular on every worker might not make any single worker’s local top 10, yet rank third globally. Either keep far more local candidates than k (say 1,000 per worker for a global top 10) and re-query all of them against the merged sketch, or partition events by tag so each tag is counted on exactly one worker and the union of local top lists is the global one. Partitioning by tag turns the hottest tag into a hot partition, which pre-aggregating counts at the producers smooths out. The full design is in Design top-K trending, and the windowing machinery in Flink and stream processing.

HyperLogLog: counting distinct items in 12 KB

The intuition: rare patterns imply many items

Hash every item to 64 bits that look random. Among distinct hashes, half start with 1, a quarter with 01, an eighth with 001, and so on: a hash whose first 1 is at position r turns up about once per 2^r distinct items. So if the highest position you have seen is 21 (twenty zeros, then a 1), you have probably seen on the order of 2^21, about 2 million, distinct items. Duplicates hash to the same value, so they never move the record; deduplication is built in.

A single maximum is far too noisy, since one lucky hash early on would claim millions. HyperLogLog, by Philippe Flajolet, Éric Fusy, Olivier Gandouet and Frédéric Meunier (2007), fixes this by splitting the stream:

1. Use the first p bits of the hash to choose one of m = 2^p registers.
2. In the remaining bits, find the rank ρ: the position of the first 1, which is the number of leading zeros plus one.
3. Set register = max(register, ρ).
4. To estimate, combine all registers with a harmonic mean: E = α_m · m² / Σ 2^(−M[j]), where α_m ≈ 0.7213 / (1 + 1.079/m) corrects a known bias.

The harmonic mean is the paper’s key step. A few registers will always see unusually long runs of zeros; an ordinary average of 2^M would let those lucky registers dominate, while the harmonic mean damps them.

The error, and where 12 KB comes from

The standard error is about 1.04 / √m, so quadrupling the registers halves the error. Redis uses p = 14:

• m = 2^14 = 16,384 registers, so the error is 1.04 / √16,384 = 1.04 / 128 ≈ 0.81%.
• The hash is 64 bits; 14 pick the register and 50 remain, so a rank is at most 51 and fits in 6 bits.
• 16,384 × 6 bits = 98,304 bits = 12,288 bytes: 12 KB, whether you count a thousand users or a billion.

A standard error of 0.81% means roughly two-thirds of estimates land within ±0.81% of the truth and about 95% within ±1.6%. For 100 million users that is typically within about ±0.8 million. The relative error stays the same as counts grow, because the memory doesn’t. The 2007 paper’s own illustration: cardinalities well beyond a billion at about 2% accuracy in 1.5 KB.

import hashlib, math

P = 14
M = 1 << P                                   # 16,384 registers
ALPHA = 0.7213 / (1 + 1.079 / M)

def add(regs, item):
    x = int.from_bytes(hashlib.blake2b(item.encode(), digest_size=8).digest(), "big")
    idx = x >> (64 - P)                      # first 14 bits pick the register
    rest = x & ((1 << (64 - P)) - 1)         # the other 50 bits
    rank = (64 - P) - rest.bit_length() + 1  # leading zeros + 1
    regs[idx] = max(regs[idx], rank)

def estimate(regs):
    e = ALPHA * M * M / sum(2.0 ** -r for r in regs)
    zeros = regs.count(0)
    if e <= 2.5 * M and zeros:               # small counts: linear counting
        return M * math.log(M / zeros)
    return e

Adding a million distinct IDs, each twice, to this sketch gave an estimate of 995,579: 0.44% low, inside one standard error, and the duplicates made no difference.

Small counts, huge counts and HLL++

The raw estimate is biased when most registers are still empty, so the original paper switches to linear counting below 2.5 · m: count the empty registers V and estimate m · ln(m / V), as the code above does. At the other end, the paper’s 32-bit hashes start to collide as counts approach 2^32 and needed a separate correction.

Stefan Heule, Marc Nunkesser and Alexander Hall described HyperLogLog++ in 2013, for Google systems such as Sawzall, Dremel and PowerDrill that estimate the cardinality of very large data sets every day:

• A 64-bit hash. It costs one extra bit per register (6 instead of 5) and removes the large-range problem until about 2^64 ≈ 1.8 × 10^19 items.
• Empirical bias correction for the middle range, where the raw estimate overshoots, using tables measured by simulation.
• A sparse representation for small sets: store only (index, rank) pairs for registers in use, at a higher precision (p′ = 25), and switch to the dense array once the list would exceed 6m bits.

Redis uses the same 64-bit hash and 6-bit registers, plus its own run-length-encoded sparse form for small counts. BigQuery’s HLL_COUNT functions implement HLL++ directly.

Merging sketches: unions, windows and the intersection trap

Both sketches merge, in different ways:

• Count-min: add the matrices cell by cell (same w, d and hashes). The result counts the combined stream.
• HyperLogLog: take the maximum of each register (same p and hash). An item always lands in the same register with the same rank, so the merged registers are exactly what one HyperLogLog would hold had it seen both streams. Redis’s PFMERGE does this, and PFCOUNT with several keys merges them on the fly.

This is what makes HyperLogLog so useful for analytics. Store one sketch per page per hour, and every coarser question (per day, per week, per site, per country) is a merge, never a re-scan of raw events. What you can’t do is subtract: once a user has raised a register, there is no removing them, so sliding windows for HyperLogLog are built by merging the small sketches inside the window rather than by subtracting old ones.

Intersections are the trap. There is no register operation for “users in both A and B”, so people reach for inclusion–exclusion: |A ∩ B| = |A| + |B| − |A ∪ B|. The result inherits the absolute error of the big numbers. Say Monday and Tuesday each had 10 million users and only 100,000 used the app on both days. The union is about 19.9 million, and its standard error alone is 0.81% × 19.9M ≈ 160,000, more than the answer you are looking for. Inclusion–exclusion only works when the overlap is a large fraction of the sets; for small overlaps, keep exact per-user data or use a sketch family designed for intersections.

Sketches in Redis and BigQuery

Redis ships both structures. HyperLogLogs are a core type; count-min sketches are part of the probabilistic types in Redis Open Source:

# HyperLogLog: distinct users per city per hour (at most 12 KB each)
PFADD   uv:{mumbai}:2026-10-27T09 u9812 u1177 u9812   # 1: a register changed
PFCOUNT uv:{mumbai}:2026-10-27T09                     # 2
PFMERGE uv:{mumbai}:2026-10-27 uv:{mumbai}:2026-10-27T00 uv:{mumbai}:2026-10-27T01
PFCOUNT uv:{mumbai}:2026-10-27

# Count-min sketch: search-term frequencies for one day
CMS.INITBYPROB q:2026-10-27 0.001 0.002          # width 2,000, depth 9
CMS.INCRBY     q:2026-10-27 biryani 1 dosa 1
CMS.QUERY      q:2026-10-27 biryani              # never below the true count

A few things worth knowing:

• An HLL is a Redis string you can move with GET and SET. A 16-byte header caches the last computed cardinality, so a single-key PFCOUNT is fast; a multi-key PFCOUNT merges on the fly, can take on the order of a millisecond, and can’t be cached.
• Small sets are cheap. Redis stores an HLL in a sparse, run-length-encoded form while few registers are set and switches to the 12,288-byte dense form as it fills.
• Cluster keys. Multi-key PFMERGE and PFCOUNT need all keys in one hash slot in a Redis cluster, hence the {mumbai} hash tag.
• The budget is easy. 500 cities × 24 hours = 12,000 hourly sketches × 12 KB ≈ 147 MB per day at most, and every daily, weekly or national figure is a merge away.
• Count-min sizing. CMS.INITBYPROB uses a base-2 version of the formulas; the docs’ example of error 0.001 and probability 0.002 yields width 2,000 and depth 9 (2 / 0.001 and ⌈log2 500⌉). Redis also advises treating results below error × total count as noise.

In a warehouse, BigQuery exposes HLL++ directly. APPROX_COUNT_DISTINCT is the one-shot version, but it can’t store partial results or re-aggregate them; the HLL_COUNT functions can:

-- One HLL++ sketch per page per day, kept for later roll-ups
CREATE TABLE analytics.daily_page_sketches AS
SELECT page_id,
       DATE(event_ts) AS day,
       HLL_COUNT.INIT(user_id, 15) AS users_sketch
FROM analytics.events
GROUP BY page_id, day;

-- Weekly unique users per page, without touching raw events again
SELECT page_id, HLL_COUNT.MERGE(users_sketch) AS weekly_users
FROM analytics.daily_page_sketches
WHERE day BETWEEN DATE '2026-10-19' AND DATE '2026-10-25'
GROUP BY page_id;

Precision can be 10 to 24 (default 15), and merging sketches of different precisions downgrades the result to the lowest. By the 1.04 / √m formula, precision 15 (32,768 registers) gives about 0.57%. Warehouses and columnar storage are covered in OLTP vs OLAP: warehouses and columnar storage.

Choosing a counting structure

Where each one shows up:

• Unique visitors per page, video or song per day: a HyperLogLog per page per period, merged for weeks and sites. See Design web analytics (Google Analytics).
• Search analytics: HyperLogLog for “how many distinct queries today”, count-min plus a heap for “which queries were most frequent”.
• Ad reach and click dedup estimates: a HyperLogLog of user IDs per campaign per hour gives unique reach for dashboards, while billing still deduplicates clicks exactly. See Design ad click aggregation.
• Trending hashtags: count-min plus a heap per minute, merged into sliding windows (Design top-K trending).
• DDoS and abuse detection: count-min over source IPs finds the heaviest senders; a HyperLogLog of distinct source IPs per destination catches distributed attacks, where each source is small but their number jumps. The HyperLogLog paper itself cites distinct-flow counts as a signal for network attacks and worms. Pair with rate limiting.

Going deeper: failure modes

Mismatched sketches merge silently

Every guarantee assumes good hashes: count-min needs (pairwise) independent hash functions per row, and HyperLogLog takes both the register and the rank from one hash. Use a quality 64-bit hash such as MurmurHash3 or xxHash, not a language’s built-in 32-bit string hash. Worse, sketches only merge if they share the same parameters (w and d, or p) and the same hash function and seed. Merge two HyperLogLogs built with different hashes and you get a confident, wrong number with no error message. Version your sketch format alongside the data.

Rare items drown in a count-min sketch

The error is a fraction of the whole stream. On a billion-event day with ε = 0.01%, anything below about 100,000 is indistinguishable from noise; Redis’s documentation says such low results should be ignored, often treated as zero. If the long tail matters, count it exactly in a batch job (see batch vs stream processing) and use the sketch only for the head.

Too many sketches

Sketches are small, but one per combination of every dimension multiplies fast. 100,000 pages × 50 countries × 3 device types × 24 hours is 360 million HyperLogLogs, about 4.4 TB if every one were dense at 12 KB. Most combinations are tiny and stay sparse, but the lesson holds: sketch at the grain you actually query, and build coarser views by merging.

Approximate is not acceptable everywhere

Cheat sheet

How to say it in the interview

“Exact distinct counts need memory for every user, which at 100 million users is gigabytes per counter, and we want them per page and per hour. So I’ll keep a HyperLogLog per page per hour: 12 KB each in Redis with a 0.81% standard error, and daily or weekly numbers are just merges, because HyperLogLogs merge by taking the max of each register. For top searches I’ll use a count-min sketch per minute with a heap of candidates. It only overcounts, by at most ε times the total, so with ε = 0.01% on a billion queries the error stays under 100,000, which is fine for items counted in millions. Workers send their sketches to a merger that sums them. Anything we bill on stays exact.”

Why does a count-min sketch never undercount? Every update adds to all d of the item’s counters and, for insert-only streams, nothing ever subtracts. So each counter holds the item’s true count plus other items’ collisions, and even the minimum is at least the true count.

How do you choose w and d? From the error you can accept and how sure you need to be. w = ⌈e/ε⌉ sets the error as a fraction of the total stream; d = ⌈ln(1/δ)⌉ sets the chance of exceeding it. Halving ε doubles the memory; each extra “9” of confidence adds about 2.3 rows.

Why a harmonic mean in HyperLogLog? A few registers always see unusually long runs of zeros. An arithmetic mean of 2^M would let those lucky registers dominate; the harmonic mean damps them, which is what brings the error down to about 1.04/√m.

Can you count users who were active on both Monday and Tuesday? Only roughly, through |A| + |B| − |A ∪ B|, and the error is about that of the union. With 10 million users a day and 100,000 overlapping, the noise (around ±160,000) swamps the answer. For retention-style questions, keep exact per-user data or use sketches designed for intersections.

How do you get top-k across many servers? Give every server the same sketch parameters and hashes. Each sends its per-minute sketch and a generous candidate list, far more than k, to a merger that sums the sketches, re-queries every candidate and keeps the top k. Alternatively, partition events by item so each item is counted on one server, and merge the local top lists.

Where to go next

• Bloom filters: the membership sketch, built on the same “bounded error for tiny memory” bargain.
• Design top-K trending: count-min plus heaps in a complete streaming design.
• Design web analytics (Google Analytics): unique visitors with HyperLogLog at scale.
• Design ad click aggregation: where approximate and exact counting have to coexist.
• Redis: HyperLogLog and the probabilistic types alongside the core data structures.
• Batch vs stream processing: sketch in the stream, reconcile exactly in batch.
• Kafka: the event log that usually feeds these pipelines.

References and further reading

1. An Improved Data Stream Summary: The Count-Min Sketch and its Applications (Cormode and Muthukrishnan, Journal of Algorithms, 2005)web.archive.orgThe sketch’s construction, w = ⌈e/ε⌉ and d = ⌈ln 1/δ⌉, the one-sided εN guarantee, and the heap-based heavy-hitters procedure (archived author copy).
2. New Directions in Traffic Measurement and Accounting (Estan and Varghese, SIGCOMM 2002)conferences.sigcomm.orgConservative update of counters and its measured accuracy gain on real traffic traces.
3. HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm (Flajolet, Fusy, Gandouet and Meunier, AofA 2007)algo.inria.frRegisters chosen by hash prefix, ranks from leading zeros, the harmonic-mean estimator, α_m, the 1.04/√m standard error and linear counting for small ranges.
4. HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm (Heule, Nunkesser and Hall, EDBT 2013)static.googleusercontent.comHLL++: the 64-bit hash, empirical bias correction and the sparse representation with higher precision.
5. Redis new data structure: the HyperLogLog (antirez, 2014)antirez.comWhy Redis uses 16,384 six-bit registers (12 KB, 0.81%), the cached cardinality, and PFMERGE as a register-wise max.
6. Redis documentation: HyperLogLogredis.ioPFADD, PFCOUNT and PFMERGE, the 12 KB and 0.81% figures, and the per-page, per-period unique-visitor pattern.
7. Redis documentation: PFCOUNTredis.ioMulti-key counts as on-the-fly unions, cached cardinality, and the sparse and dense (12,288-byte) encodings.
8. Redis documentation: Count-min sketchredis.ioCMS.INITBYPROB, CMS.INCRBY, CMS.QUERY and CMS.MERGE, the width and depth chosen for a given error, and treating low counts as noise.
9. Redis documentation: Bloom filter (set memory comparison)redis.ioRedis’s estimate of set memory per member, about 192 bits of overhead plus the value, used for the exact-counting arithmetic.
10. BigQuery documentation: HyperLogLog++ functionscloud.google.comHLL_COUNT.INIT, MERGE, MERGE_PARTIAL and EXTRACT, precision 10 to 24 (default 15), and how APPROX_COUNT_DISTINCT differs.