Skip to content

Approximate counting

Counting with a stated error instead of an exact figure: HyperLogLog for distinct items, a count-min sketch for item frequencies, sampling for rough totals. The design question it raises is whether the number has to be exact.

On this page

What it is

Approximate counting trades an exact figure for an estimate with an error you can state in advance, usually to save memory or write contention. The cost it avoids is real: counting distinct items exactly takes memory proportional to how many distinct items there are, because you have to remember each one to avoid counting it twice. A sketch (a compact summary of the stream) replaces that with a fixed block of counters whose size you choose from the error you can accept, so memory stays bounded however many items pass through.

Two different questions hide under the word "count", and they need different sketches. How many distinct items have I seen? is cardinality estimation, and HyperLogLog is the usual answer. How many times has this one item appeared? is frequency estimation, and a count-min sketch is the usual answer. Neither tells you which items were seen: the sketch holds state, not elements, so if you need the member list you need a set.

How HyperLogLog works. Each item is hashed into what looks like a uniformly random bit string. Among many random bit strings, the longest run of leading zeros hints at how many you've seen: if the longest run is n zeros, about 2 to the power n items have passed. One such guess has a large variance, so the algorithm uses the first few bits of the hash to pick one of m registers and lets each register keep its own maximum; the count combines the registers with a harmonic mean and a correction constant. For small counts the estimate is biased, so the original paper proposes a different method (Linear Counting) below a threshold. That paper reports counting past a billion distinct items with a standard error near 2% in about 1.5 kB, and merging two sketches is taking the larger value in each register pair, which yields the sketch of the union.

HyperLogLog in Redis. Redis has shipped it since version 2.8.9; the three commands you'll use are PFADD to add items, PFCOUNT for the estimate and PFMERGE to combine keys. The current documentation puts the memory at up to 12 KB per key, much less while a key has seen few items, with a standard error of 0.81%. A HyperLogLog is stored as a Redis string, so GET and SET serialize and restore it, and a merged key gives an estimate of the distinct items across all its sources.

Count-min sketch. A fixed-size table of counters, sized from the error you can accept rather than from the number of items. Hash collisions add to counters, so the estimate can be too high but not too low, and the error is measured relative to the total of everything added: you choose a threshold and a probability of staying within it. That makes small counts unreliable: the Redis documentation advises treating results under the error threshold as noise, often as zero. In Redis you size it by tolerance: CMS.INITBYPROB key 0.001 0.002 asks for error within 0.1% of the total with a 0.2% chance of exceeding it, and the resulting sketch is 2000 wide and 9 deep; CMS.INCRBY adds, CMS.QUERY estimates, CMS.MERGE combines.

Analytics warehouses expose the same ideas as SQL functions. BigQuery has APPROX_COUNT_DISTINCT and APPROX_TOP_COUNT among its approximate aggregate functions, alongside a separate family of HyperLogLog++ functions for working with the sketch itself.

When to use it

Reach for HyperLogLog when the question is distinct items at a scale where a set per key would be large: unique viewers per video, unique visitors per page per day, distinct IPs hitting an endpoint. Millions of keys at a bounded 12 KB each is a budget you can state; millions of sets of user IDs is not. Keep one sketch per period and per dimension (day, page, country) and merge them for rollups: the weekly figure is a merge of seven daily sketches, with no recount of the raw events.

Reach for a count-min sketch when the question is how often particular items appear and the heavy hitters are what matter: trending hashtags, the hottest keys in a cache, products that dominate a day's sales. The Redis documentation's own example is one sketch per day of product sales, which gives a reasonable figure for the top sellers while the long tail is ignored. The sketch answers "how often did X appear" for an X you supply; to discover the top items, pair it with a small list of candidates (a sorted set of the current leaders, for example) that you check and update as events arrive.

When not to

Keep the count exact when being wrong has a cost you can name: money, remaining stock in a sale, a quota that gates access, anything audited. An estimate that's 1% high on a payout is a bug, not a trade-off. Also stay exact when the distinct set is small or bounded: a set of a few hundred IDs is cheap, and a plain hash of counters for a known, bounded key space is exact and small.

Don't use a count-min sketch to read rare items. Its error is relative to the total of everything added, so an item seen a handful of times among billions of events can read far higher than the truth, and such values should be treated as noise. If rare items matter (fraud signals, first-time users), track those keys exactly in a structure of their own; untargeted sampling tends to miss them too.

A high write rate is often better met without approximation. If a single like counter is a hot key, split it into N shards, increment one at random, and sum the shards on read: the total stays exact and the write load spreads out. See Hot keys and hot partitions. Approximation earns its place when memory is the constraint, when the answer is a distinct count that sharding does not make cheap, or when you are willing to trade accuracy for less coordination between writers.

Compared

ApproachWhat it answersMemoryErrorWhen it is the right pick

Exact set or hash of counters

Distinct members, or exact per-key counts

Grows with the number of distinct items

None

Small or bounded key spaces, or when you need to know which items appeared

Sharded exact counter

One total under heavy writes

One slot per shard

None

Totals that must be exact (stock, money) where the problem is write contention, not memory

Sampling (count 1 in k, multiply)

A rough total or breakdown

Proportional to the sample

Depends on sample size

Rough traffic breakdowns where a sketch per dimension would be overkill

HyperLogLog

How many distinct items

Fixed: up to 12 KB per key in Redis

Standard error 0.81% in Redis

Very large distinct counts, and rollups by merging per-period sketches

Count-min sketch

How often one item appeared

Fixed width times depth (2000 by 9 for 0.1% and 0.2%)

Overestimates; likely within a threshold set relative to the total added, with a configured chance of exceeding it

Heavy hitters and trending items, where the long tail can be ignored

In a picture

user_idHash to bits

Step 1 of 4

Hash the item

Each item (a user ID, an IP) goes through a hash function so the bits look uniformly random.

How to say it in an interview

The common mistake

Quiz

Which question does a HyperLogLog answer?
An item was added twice to a count-min sketch that has seen a billion events. What can its query return?
You keep a HyperLogLog of unique visitors per day. How do you get the month's unique visitors?
Which of these should not be an approximate count?

Questions that use this

Related

Sources

  1. Redis documentation: HyperLogLog
  2. Redis documentation: Count-min sketch
  3. Wikipedia: HyperLogLog
  4. BigQuery documentation: Approximate aggregate functions
Sign in to report a mistake