Probabilistic Data Structures: Bloom Filter, Count-Min Sketch and HyperLogLog

Version note: The code in this post was built with .NET 10, C# 14 and System.IO.Hashing 10.0.15 and verified with xUnit v3 4.0.2 tests.

Guess First

Bookstore, the online bookstore used as the shared example across this site's series, checks "has this e-mail already registered?" when the user leaves the e-mail field of the sign-up form. There are 1,000,000 registered users and every check is a database query. To avoid most of these queries we want to keep the e-mails in memory. Roughly how many MB does a HashSet<string> take? And how many MB does a structure take that is never wrong when it says "no" and is wrong 1 percent of the time when it says "yes": 50, 10, or 1?

Second question: there are 1.5 million visits and a few hundred thousand unique visitors a day. How many KB do you need to know the number of unique visitors with an error below 1 percent?

Bloom Filter: k Hashes and a Bit Array

The structure Burton Bloom described in 1970 consists of an array of m bits and k hash functions. Every added item sets k positions to 1. A query looks at the same k positions: if even one is 0, the item was definitely never added; if all are 1, it was probably added, because other items may have filled those bits.

// m bits, k hash positions per item. "false" = definitely never added; "true" = probably added
public sealed class BloomFilter
{
    private readonly ulong[] _bits;

    public void Add(string item)
    {
        (ulong h1, ulong h2) = ItemHash.Hash128(item);
        for (int i = 0; i < HashCount; i++)
        {
            long bit = Position(h1, h2, i);
            _bits[bit >> 6] |= 1UL << (int)(bit & 63);
        }
    }

    public bool MightContain(string item)
    {
        (ulong h1, ulong h2) = ItemHash.Hash128(item);
        for (int i = 0; i < HashCount; i++)
        {
            long bit = Position(h1, h2, i);
            if ((_bits[bit >> 6] & (1UL << (int)(bit & 63))) == 0) return false; // one zero bit is enough
        }

        return true;
    }

    // Double hashing (Kirsch and Mitzenmacher): k positions from two hashes
    private long Position(ulong h1, ulong h2, int i) => (long)((h1 + (ulong)i * h2) % (ulong)BitCount);
}

You do not need to write k independent hash functions. Kirsch and Mitzenmacher's 2006 work shows that k positions generated from two hashes as h1 + i·h2 do not change the false positive rate in practice. We get both hashes from a single computation: ItemHash splits the XxHash128 value, from the System.IO.Hashing package, of the item's UTF-8 bytes in two. We do not use string.GetHashCode() because, as we saw in the sixth post of this series, it runs with a different seed in every process; a filter written to disk or shared with another server would be meaningless with it.

Sizing: The Formula and the Measurement

In a filter with m bits and k hashes into which n items have been added, the false positive rate is about (1 − e^(−kn/m))^k. If the target rate is p, the required number of bits and the best number of hashes follow from this formula:

// n expected items, p target false positive rate: m = -n ln p / (ln 2)^2, k = (m / n) ln 2
public static BloomFilter ForCapacity(long expectedItems, double falsePositiveRate)
{
    double m = -expectedItems * Math.Log(falsePositiveRate) / (Math.Log(2) * Math.Log(2));
    int k = Math.Max(1, (int)Math.Round(m / expectedItems * Math.Log(2)));
    return new BloomFilter((long)Math.Ceiling(m), k);
}

For 1 percent: 9.6 bits per item and 7 hashes. I ran the opening scenario: I added 1,000,000 e-mails, then queried 1,000,000 e-mails that were never added.

bloom: m=9,585,088 bits (1.14 MB), k=7
HashSet<string> with the e-mails: 162.6 MB
false negatives: 0
false positives: 10,089 / 1,000,000 = 1.01 % (formula 1.00 %)
after 3,000,000 adds: 43.64 % (formula 43.60 %)

The HashSet value was measured as a GC.GetTotalMemory difference and includes the strings themselves; the exact number depends on the environment, but the order of magnitude does not: 1.14 MB against hundreds of MB. The Bloom filter does not store the e-mails, only bits. The measured rate matches the formula and there are no false negatives; every added e-mail answered "probably present".

The last line is the structure's most important warning. The filter was sized for 1 million; after 3 million items were added, most bits became 1 and 44 percent of new e-mails got "probably present". No exception, no log; the filter just becomes useless. Since it does not know which items were added, a Bloom filter cannot be grown later either; you have to build a bigger filter from scratch.

In Bookstore the flow is: if the filter says "no", the e-mail is definitely new and there is no need to go to the database; if it says "yes", the database is asked. So only e-mails that really are registered, plus about 1 percent of new ones, reach the database. The filter is not a security measure but a query saving: whether to tell the user "this e-mail is registered" is a separate decision.

No Deletes: Counting and Cuckoo Filters

When a user deletes their account, we cannot remove their e-mail from the filter: setting its bits to 0 produces false negatives for other e-mails that share those bits, breaking the structure's only guarantee. There are two common solutions. A counting Bloom filter keeps a small counter instead of each bit (usually 4 bits); adding increments, deleting decrements, at the cost of about 4 times the memory. A cuckoo filter (Fan, Andersen, Kaminsky and Mitzenmacher, 2014) keeps short fingerprints of items in a table using cuckoo hashing; it supports deletion and can take less space than a Bloom filter at low false positive rates. If deletions are rare, the simplest solution is usually to rebuild the filter periodically from the source.

Count-Min Sketch: Approximate Frequencies

A Bloom filter answers "is it there?"; for "how many times?" there is the Count-Min Sketch, published by Cormode and Muthukrishnan in 2005. It is a table of counters with d rows and w columns: every item increments one counter in each row, and a query returns the smallest of the item's d counters.

public void Add(string item, long count = 1)
{
    (ulong h1, ulong h2) = ItemHash.Hash128(item);
    for (int row = 0; row < Depth; row++) _counts[row, Column(h1, h2, row)] += count;
    TotalCount += count;
}

public long Estimate(string item)
{
    (ulong h1, ulong h2) = ItemHash.Hash128(item);
    long min = long.MaxValue;
    for (int row = 0; row < Depth; row++) min = Math.Min(min, _counts[row, Column(h1, h2, row)]);
    return min; // every row over-counts because of collisions; the smallest is the closest
}

The guarantee is one-sided: the estimate is never below the true count and, with probability 1 − δ, at most ε·N above it (N being the total count). The dimensions follow from that: w = ⌈e/ε⌉, d = ⌈ln(1/δ)⌉. For Bookstore I generated 2,000,000 views over a 100,000-book catalog, with popularity falling off as 1/rank, and measured with ε = 0.001 and δ = 0.01:

sketch: 2719 x 5 counters = 106 KB, distinct books viewed: 94,026
9780000000000: exact 165,696, sketch 166,074
9780000000001: exact  82,257, sketch  82,406
9780000000002: exact  55,215, sketch  55,410
over-count: max 1,153, average 197.5, bound epsilon*N = 2,000
a book viewed once: exact 1, sketch 153

For the most viewed books the error is 2 to 4 per thousand; the worst over-count is also below the 2,000 bound. The last line shows where the sketch does not help: for a book viewed once it says 153. The error is absolute (ε·N), not relative; small counts get lost in the noise of collisions. Count-Min Sketch is for heavy hitters, the most frequent items: for "the 10 most viewed books" you combine the sketch with a 10-element min-heap as in the thirteenth post of this series, comparing the estimate with the heap's smallest on every view. The W-TinyLFU from the twenty-third post estimated frequencies with this structure too.

HyperLogLog: Counting Uniques with 16 KB

The exact way to count unique visitors is to keep every identifier in a set; memory grows with the number of uniques. HyperLogLog, by Flajolet, Fusy, Gandouet and Meunier in 2007, rests on a different observation: in random hashes, seeing k zero bits at the start happens about once in 2^k distinct values. Remembering the longest run of zeros roughly tells you how many distinct values you have seen. Because a single estimate is very noisy, the first p bits of the hash send the item to one of 2^p registers, and the estimates are combined with a harmonic mean:

public void Add(string item)
{
    ulong hash = XxHash3.HashToUInt64(Encoding.UTF8.GetBytes(item));
    int index = (int)(hash >> (64 - _p));                          // first p bits pick the register
    ulong rest = (hash << _p) | (1UL << (_p - 1));                 // guard bit keeps rho bounded
    byte rho = (byte)(BitOperations.LeadingZeroCount(rest) + 1);   // position of the first 1 bit
    if (rho > _registers[index]) _registers[index] = rho;
}

// The union of two sets: the larger value of each register
public void Merge(HyperLogLog other)
{
    if (other._p != _p) throw new ArgumentException("Precision must match.", nameof(other));
    for (int i = 0; i < _registers.Length; i++)
        _registers[i] = Math.Max(_registers[i], other._registers[i]);
}

Count applies the formula from the paper; for small counts it switches to linear counting, which works with the number of empty registers. The standard error is 1.04/√m; with p = 14 that is 16,384 registers and 0.81 percent. I generated a two-day visit stream, 1.5 million visits per day:

registers: 16,384 (1 byte each), standard error 0.81 %
monday unique: exact 390,808, HLL 391,358
monday + tuesday: exact 590,657, HLL 595,324

The error is 1.4 per thousand for Monday and 0.8 percent for the union of the two days. The answer to the second question is 16 KB: we used one byte per register. Redis provides the same precision with at most 12 KB by packing registers into 6 bits. The real strength is in Merge: if you keep each day's HLL, you get weekly or monthly uniques by merging the days; the same visitor is not counted twice. You cannot add them (adding two days' uniques counts shared visitors twice), and you cannot take an intersection directly. Since HLL does not store identifiers, it cannot answer "did this user come yesterday?" either.

Ready-Made Solutions: Redis

None of these structures are in the BCL. In production you will mostly use the ones in Redis: PFADD, PFCOUNT and PFMERGE for HyperLogLog, and separate command groups for Bloom filter, cuckoo filter, Count-Min Sketch and Top-K. The advantage is that the structure is shared by all servers and is persistent. The commands, memory settings and usage with StackExchange.Redis are in the Redis series post "Special Data Types: Bitmaps, HyperLogLog, Geospatial and Probabilistic Structures (Bloom, Cuckoo, Top-K)"; the goal here was to know the algorithm behind those commands.

In Production

Size for growth. Build the Bloom filter not for today's number of users but for the number it will reach before its next rebuild. Count the added items and rebuild the filter with a bigger size when ExpectedFalsePositiveRate exceeds the target.

Pin the hash. If you write the filter to disk or share it between servers, the hash function and seed are part of the contract. Changing the hash silently breaks the existing filter: added items start getting "definitely not".

Explain the error margin to the business. "391 thousand unique visitors today" is an estimate; the dashboard should say "approximately" and the error margin should be documented.

Measure whether you really need it. For 10,000 items a HashSet is a few hundred KB and exact. These structures earn their place with millions of items or counters distributed across many servers.

Common Pitfalls

Reading the Bloom filter's guarantee backwards. The "definitely not / probably yes" structure makes it wrong to trust a "yes" and skip the database. A 1 percent false positive means telling a new user "this e-mail is already registered".

Using an approximate count where exactness is required. Billing, stock, campaign quotas or legal reports are not computed with HLL or Count-Min Sketch. Reading a book's sales count from a sketch means billing the customer for the difference between 153 and 1.

Overfilling the filter. As in the measurement, tripling the number of items turns 1 percent into 44 percent, and nobody notices; track the fill ratio as a metric.

Using Count-Min Sketch for rare items. The error is proportional to the total count; the counts of rarely seen items become meaningless.

A Small Experiment

★☆☆ Add a Count property that tracks the number of added items and a FillRatio property that returns the fraction of set bits to BloomFilter. What is the fill ratio after 1 million e-mails? In theory it should be about 50 percent; why?

★★☆ Write a TopK class that combines CountMinSketch with a 10-element min-heap, and compare the top 10 books it finds on the same 2,000,000 views with the exact result.

★★★ Set the precision of HyperLogLog to 10, 12, 14 and 16 and count the same 390,808 unique visitors with 20 different seeds for each. Does the error distribution you measure match 1.04/√m?

In this post we gave up exactness on purpose and kept the error under control by measuring it. In the last post of the series we look at randomness itself: correct and incorrect shuffles, sampling from a stream, weighted selection, and the deterministic hash that keeps a user in the same group of a feature flag percentage on every request.