Probabilistic data structures in Go, part 2

Probabilistic data structures give you approximate answers to questions about the data they handle. Does the set contain a certain item? How many unique items are in the collection? What is the 99th percentile in a stream of numbers? How similar are two sets? Unlike deterministic structures, the answers might not be exact, but in return, you can save a lot of memory.

Previously, we reviewed the following data structures: Bloom filter (for checking if an item is in a set), Count-min sketch (for counting items), HyperLogLog (for counting unique items), T-digest (for finding quantiles), and Top-k (for finding the most frequent items).

In this post, we'll talk about other probabilistic structures and compare them to the ones we've already covered. We'll look at how they work and what kinds of guarantees they provide.

All examples use unsure — a package that implements these structures in Go.

Binary fuse filter • UltraLogLog • Log-linear histogram • MinHash

Binary fuse filter

A binary fuse filter is a set that trades certainty for space, like a Bloom filter1. It can tell you that an item is definitely not in the set, or that it probably is (which might be a false positive). The filter doesn't store the items, so it's much more compact than a regular set.

Unlike a Bloom filter, a binary fuse filter is static: you build it once from all the items, and you can't add more later. In exchange, it uses less memory than a Bloom filter with the same false positive rate. For example, a fuse filter for 1,000,000 items with a 0.39% false positive rate takes 1.13 MB (9 bits per item), while a Bloom filter takes 1.51 MB (12 bits per item).

This makes binary fuse filters a good fit for data that is written once and read many times, like the key set of an immutable file in a database (to skip files that don't have the key), or a list of known bad items, such as leaked passwords or malicious URLs.

items := [][]byte{[]byte("alice"), []byte("bob")}

// An 8-bit filter: 0.39% false positive rate.
filter := fuse.New[uint8](slices.Values(items), len(items))

filter.Contains([]byte("alice")) // true
filter.Contains([]byte("carol")) // false (or, rarely, true)

The fingerprint type (T in New[T]) determines the false positive rate and the memory use:

TypeFalse positive rateBits per item
uint80.39%9
uint160.0015%18
uint322.3e-1036

The constructor takes an iterator of items to add to the filter and the expected number of items (0 if unknown). The number is only used to preallocate memory, so a good estimate makes the build faster.

You can check if an item is in the filter, but you cannot add or delete an item, count the number of items, or iterate over them.

How it works

The filter2 is an array of b-bit fingerprints (for example, b = 8 for uint8). Each item is hashed to a 64-bit value h, which gives the item's fingerprint f (b bits computed from h) and three positions in the array (cells). The array is filled so that for every item, the XOR of its cells equals f.

        ┌──────┐               ┌──► f  (b bits)
item ──►│ hash │──► h ─────────┤
        └──────┘               └──► i0, i1, i2

           i0          i1          i2
┌───┬───┬──▼──┬───┬───┬──▼──┬───┬──▼──┬───┐
│   │   │ F0  │   │   │ F1  │   │ F2  │   │   F0 ^ F1 ^ F2 == f
└───┴───┴─────┴───┴───┴─────┴───┴─────┴───┘

To check an item, you compute h, look up its three cells, and compare their XOR with f. For an item in the set, they always match. For any other item, the XOR is a random b-bit value, which matches f with probability 2^-b.

Each check reads three cells, so for large filters it's three cache misses, against one for a blocked Bloom filter. However, since the reads are independent, the CPU can do them concurrently, so the checks are about as fast as with a Bloom filter.

The filter uses the local wyhash3 implementation for hashing. It performs roughly the same as xxh34 but has a much simpler implementation, without SIMD or assembly.

Benchmarks

Here's an excerpt from the full benchmarks5, comparing unsure to xorfilter6 (binary fuse by the authors of the paper) and bloom (unsure's own Bloom filter) with 8-bit fingerprints (ns/op, lower is better):

OperationItemsunsurexorfilterbloom
Build (per item)10K232513
1M303112
Contains10K6.28.09.3
1M7.09.310.2
50M394240

Memory, bits per item (lower is better):

ItemsFingerprintunsurexorfilterbloom
100K8-bit9.509.5012.45
10M8-bit9.029.0212.10
10M16-bit18.0418.0427.99

Unsure is the same size as xorfilter (same layout) with up to 25% faster checks. Compared to the Bloom filter, it uses up to 36% less memory, with checks as fast or faster, but up to 2.5× slower builds.

UltraLogLog

UltraLogLog is a unique items counter that trades accuracy for space, like HyperLogLog7. It tells you approximately how many distinct items it has seen, no matter how many times each one appeared. UltraLogLog doesn't store the items, so it's much more compact than a regular set.

UltraLogLog is a newer design (Otmar Ertl, 2024) that uses the space more efficiently: for the same error, it needs about 43% less memory than HyperLogLog. For example, a HyperLogLog sketch with 0.81% standard error takes 16 KB, while an UltraLogLog sketch with 0.86% error takes 8 KB. However, adding, counting, and merging are slower than with HyperLogLog.

UltraLogLog is useful in the same places as HyperLogLog: counting unique visitors, unique search queries, or distinct values in a database column, possibly across many machines or segments.

// Standard error about 0.9% of the true count.
sketch := ull.New()

sketch.Add([]byte("alice"))
sketch.Add([]byte("bob"))
sketch.Add([]byte("alice"))
sketch.Add([]byte("carol"))

sketch.Count() // 3 (approximately)

You can merge sketches to get the total number of unique items from all of them, without counting shared items twice.

home := ull.New() // visitors to the home page
docs := ull.New() // visitors to the docs
// ...
home.Merge(docs)
home.Count() // visitors to either page

The sketch has one setting: the precision p, which gives a relative standard error of 0.782/√(2^p). The default is p=13 with 0.86% error in 8 KB, close to the common HyperLogLog default (0.81% in 16 KB).

You can add items to a sketch, get the estimated count, and merge sketches. You cannot check if a specific item was added, remove items, or list them.

How it works

HyperLogLog hashes each item and uses the first p bits of the hash to pick one of m = 2^p registers. It calculates the rank (the number of leading zeros in the rest of the hash, plus one) and keeps the highest rank it has seen in the register. Seeing a rank of k suggests there were about 2^k items in the register. The count is estimated from all the registers together.

                      p bits
        ┌──────┐   ┌──────────┬────────────────────────┐
item ──►│ hash │──►│ 01101001 │ 0001101...             │
        └──────┘   └────┬─────┴───────────┬────────────┘
                        │ register i      └ rank = 3 zeros + 1 = 4
          ┌───┬───┬───┬─▼─┬───┬───┬───┬───┬───┬───┐
registers │ 3 │ 0 │ 5 │ 2 │ 1 │ 0 │ 4 │ 2 │ 0 │ 1 │  2 → 4
          └───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘

A HyperLogLog register loses some information: it only keeps track of the highest value, not whether any slightly lower values were seen. These lower values show up at least as often as the highest one, so they can tell a lot about the count.

UltraLogLog8 uses the registers more efficiently. Each register is still one byte, but it stores the highest rank k in the upper 6 bits, and whether k−1 and k−2 were seen in the lower 2 bits:

              k = 5        k-1 k-2
          ┌───────────────┬───┬───┐
register  │ 0 0 0 1 0 1   │ 1 │ 0 │  saw 5 and 4, but not 3
          └───────────────┴───┴───┘
          ┌───────────────┬───┬───┐
add k=6:  │ 0 0 0 1 1 0   │ 1 │ 1 │  saw 6, 5, 4
          └───────────────┴───┴───┘

The count estimate uses the FGRA estimator from the UltraLogLog paper. Each register adds a weight based on its value, and the count is calculated as a power of the sum of the weights. Nearly empty and nearly full sketches get special handling, so the estimate stays accurate from zero to billions of items, without bias tables or a separate formula for small counts.

Unsure keeps a histogram of register values (256 four-byte counters, 1 KB) updated as the registers change. This way, Count reads the histogram instead of scanning all the registers. Merge checks 8 registers at a time using a few bitwise operations to find which ones the other sketch would change, and only updates those.

The item is hashed once with wyhash, and the 64-bit hash is split into the register index and the rank.

Benchmarks

Here's an excerpt from the full benchmarks9, comparing UltraLogLog to unsure's own HyperLogLog and axiom10 (HyperLogLog with LogLog-Beta estimator and sparse mode) (ns/op, lower is better):

OperationpSizeullhllaxiom
Add101 KB8.15.57.6
1416 KB8.05.77.7
18256 KB9.48.38.0
Count101 KB1656817,700
1416 KB16163348,000
18256 KB173574,650,000
Merge101 KB2,9007201,740
1416 KB51,20020,20058,500
18256 KB818,000341,000955,000

Accuracy and memory, relative RMSE over 1,000 sketches (lower is better):

Distinct itemsull p=13hll p=14axiom p=14
1,0000.66%0.54%0.01%
40,0000.73%0.68%0.69%
1,000,0000.86%0.79%0.82%
Memory9.1 KB16.3 KB16.1 KB

UltraLogLog provides the same accuracy as HyperLogLog with almost half the memory. However, adding, counting, and merging are noticeably slower.

Log-linear histogram

A log-linear histogram is a summary of a stream of numbers that trades accuracy for space. It can give you an approximate median, 99th percentile, or any other quantile of the data. It can also estimate what fraction of the numbers are below a certain value (the CDF). The histogram doesn't store the numbers, so it's much more compact than a sorted list.

For example, to find the exact 99th percentile of 1,000,000 response times, you'd have to keep all of them. With 64-bit floats, that takes 8 MB. A log-linear histogram estimates the same percentile within 0.39% of its true value using about 14 KB — almost 600 times less.

The error is relative to the value: if the true 99th percentile is 200 ms, the histogram returns a value between 199.2 and 200.8 ms. This guarantee applies to every quantile, from the median to the most extreme outliers. The size of the histogram doesn't depend on the number of values, only on the accuracy you choose and on how wide the range of the values is.

A log-linear histogram is useful when you need percentiles for positive values that cover a wide range, like latencies, file sizes, or prices.

// Response times in milliseconds.
hist := loghist.New()

hist.Add(12.5)
hist.Add(8.1)
hist.Add(130.0)
// ...

hist.Quantile(0.5)  // median
hist.Quantile(0.99) // 99th percentile
hist.CDF(100)       // fraction of responses faster than 100 ms

You can merge histograms to gather data from multiple machines or segments (like by hour, endpoint, or region). Merging is exact: a merged histogram is the same as if it had received all the values directly.

east := loghist.New() // latencies on one server
west := loghist.New() // latencies on another
// ...
east.Merge(west)
east.Quantile(0.99) // 99th percentile across both servers

The histogram has two settings: relative error and value range. By default, the error is 0.0039 (0.39%) and the range is from 1e-9 to 1e18. Lowering the error or increasing the range uses more memory.

You can add numbers to a histogram, estimate quantiles and the CDF, and merge histograms. You cannot remove numbers or list them.

How it works

A histogram splits the range of values into buckets and counts how many values are in each one. To estimate a quantile, it adds up the counts starting from the lowest bucket until it reaches the requested rank, then returns a value from that bucket. The accuracy of the estimate depends on how wide the bucket is.

With buckets that have equal widths, like 0–10, 10–20, and so on, every estimate has the same absolute error of ±5 around the bucket's midpoint. So the relative error is very large for small values and unnecessarily small for large values:

0       10      20      30     970     980     990     1000
├───────┼───────┼───────┼─ ··· ─┼───────┼───────┼───────┤
    └ 5 ± 5: ±100%                   995 ± 5: ±0.5% ┘

A logarithmic histogram solves this by making each bucket's width proportional to its value. For example, if the bucket boundaries are powers of 1.02 (1, 1.02, 1.0404, ...), the end of each bucket is 2% larger than its start, so any value in the bucket is within about 1% of the bucket's midpoint. DDSketch11 uses this method. The downside is that finding the right bucket for a value means you have to calculate a logarithm, which is relatively slow.

A log-linear histogram gets almost the same result with cheaper math. First, it splits the values into ranges between powers of two: 1–2, 2–4, 4–8, and so on (these are called octaves). Then it splits every octave into the same number of equal-width buckets. For example, here are three octaves with 4 buckets each:

1       2               4                               8
├─┬─┬─┬─┼───┬───┬───┬───┼───────┬───────┬───────┬───────┤
4 buckets   4 buckets               4 buckets

Each octave is twice as long as the previous one, so its buckets are twice as wide, and the bucket width grows with the values, as in a logarithmic histogram. Finding the right bucket only takes a few bit operations instead of calculating a logarithm.

HdrHistogram12 is the best-known log-linear histogram. It records integers: the position of the highest 1 bit of a number determines its octave, and the next few bits determine the bucket within the octave.

Unsure works with float64 numbers and finds the bucket in a similar way to HdrHistogram.

IEEE 754 double-precision format

A float64 in Go (and most other languages) is made up of three parts:

  • a sign bit,
  • an 11-bit exponent e (stored as 1023 + e to avoid negative values),
  • and a 52-bit mantissa f.

The number's value is 1.f × 2^e, where 1.f is a binary fraction between 1 and 2.

The exponent determines the octave, from 2^e to 2^(e+1). The top m bits of the mantissa determine one of the 2^m equal buckets within the octave.

For example, here's the number 5.25 with m=3 (8 buckets per octave). In binary, 5.25 = 1.0101₂ × 2², so the exponent is 2 (stored as 1025), and the mantissa starts with 0101:

5.25 = 1.0101₂ × 2²

sign   exponent     top m   rest of the mantissa
┌───┬─────────────┬─────┬─────────────────────────┐
│ 0 │ 10000000001 │ 010 │ 1000000000 ... 00000000 │
└───┴──────┬──────┴──┬──┴──┬──────────────────────┘
           │         │     └── ignored
           │         └── bucket 2 of 8
           └── 1025 = 2 + 1023: octave [4, 8)

4                               8
├───┬───┬───┬───┬───┬───┬───┬───┤
  0   1   2   3   4   5   6   7
          └ 5.25 lands in bucket 2: [5, 5.5)

Add finds the bucket for the given number and increases the count. Merge adds the counts bucket by bucket. Quantile adds up the counts from the closer end (the leftmost bucket for q ≤ 0.5, the rightmost bucket otherwise) until it reaches the rank.

The number of mantissa bits m comes from the requested error: the constructor picks the smallest m for which the maximum error doesn't exceed the requested one. The default is m=7: 128 buckets per octave and an error of 0.39%.

Log-linear histogram vs. t-digest

A t-digest13 also estimates quantiles, but it limits the error in ranks: Quantile(0.99) returns a value whose rank is close to 99%. A log-linear histogram limits the error in values: Quantile(0.99) returns a value close to the true 99th percentile.

In the middle of the data, the two are pretty similar. But in a long tail, values at nearby ranks can be very different, so even a small error in rank can lead to a big difference in value. Here is the mean relative error of an 8.5 KB t-digest (δ=100) on 1M values from three distributions: lognormal (as in the benchmarks), Pareto with α=1.5 (a longer tail), and uniform between 1,000,000 and 2,000,000 (no tail):

QuantileLognormalParetoUniform
0.50.12%0.09%0.009%
0.991.7%5.6%0.015%
0.9998.7%67%0.009%
0.999983%868%0.004%

A log-linear histogram of about the same size (1% error, 8 KB) has an error below 0.78% for all these cases.

So a log-linear histogram is better for latencies, sizes, and other positive measurements with long tails. A t-digest is better when you need a fixed size no matter what the values are, or when the values can be arbitrarily close to zero.

Benchmarks

Here's an excerpt from the full benchmarks14, comparing unsure to hdr15 (log-linear, integers only, fixed range) and dd16 (DDSketch, logarithmic buckets) with a lognormal distribution (ns/op, lower is better):

OperationErrorunsurehdrdd
Add1%4419
0.4%4419
0.1%4419
Quantile1%482831,750
0.4%901,7083,100
0.1%3371,71211,967
Merge1%33416,369302
0.4%657115,052808
0.1%3,249115,0182,862

Mean relative error at the requested 0.1%, over 1M values (lower is better):

Quantileunsurehdrdd
0.50.033%0.033%0.050%
0.990.038%0.037%0.048%
0.9990.027%0.019%0.039%
0.99990.016%0.002%0.025%

Memory after adding 1M values (lower is better):

Errorunsurehdrdd
1%8 KB40 KB6 KB
0.4%14 KB264 KB13 KB
0.1%56 KB264 KB40 KB

Unsure adds values as fast as hdr and 5× faster than dd, queries 5–19× faster than hdr and about 35× faster than dd, and merges about as fast as dd and 35–175× faster than hdr. It's slightly less accurate than hdr (using 5× less memory), and more accurate than dd (using 1.4× more memory).

MinHash

MinHash estimates how similar two sets are. It summarizes each set in a short fixed-size signature (for example, 256 numbers). Comparing two signatures gives the approximate Jaccard similarity of the sets: |A∩B| / |A∪B|, the proportion of unique items that both sets share.

The size of a signature doesn't depend on the size of the set, so you can compare two sets of a million items each just by comparing 256 pairs of numbers instead of checking every item. Plus, each set's signature is only calculated once, so comparing lots of sets to each other is relatively cheap.

MinHash is useful for finding near-duplicate documents, like web pages or essays (represented as sets of words or 3-word phrases). It's also useful for finding similar user profiles (as sets of liked items) or overlapping datasets (as sets of keys).

// Two documents as sets of words.
strA := "the quick brown fox jumps over the lazy dog"
docA := minhash.New(256)
for w := range strings.FieldsSeq(strA) {
    docA.Add([]byte(w))
}

strB := "the quick brown cat jumps over the lazy dog"
docB := minhash.New(256)
for w := range strings.FieldsSeq(strB) {
    docB.Add([]byte(w))
}

sigA, sigB := docA.Signature(), docB.Signature()
sigA.Similarity(sigB) // 0.75 (true value 7/9 = 0.78)

The MinHash sketch has one setting: the signature size k, which gives a standard error of √(J(1−J)/k) for true similarity J. For example, with k=256 and J=0.5:

  • 68% of estimates are within ±3.1 pp of J (0.47–0.53),
  • 95% within ±6.2 pp (2·stdErr),
  • 99.7% within ±9.4 pp (3·stdErr).

You can add items to a sketch, merge sketches, and get and compare signatures. You cannot check if a specific item was added, count the items, remove them, or list them.

How it works

Classic MinHash17 hashes every item with k different hash functions. Here are two sets, A = {fox, cat, dog, owl} and B = {fox, dog, emu}, and their item hashes for k=4:

item   h1     h2     h3     h4     in A   in B
fox    0.07   0.52   0.66   0.38    ✓      ✓
cat    0.21   0.15   0.80   0.91    ✓
dog    0.48   0.33   0.09   0.74    ✓      ✓
emu    0.63   0.27   0.44   0.12           ✓
owl    0.90   0.71   0.58   0.29    ✓

For each hash function, the set keeps only the smallest hash value among its items. These k minimums are the set's signature. To estimate the similarity of two sets, compare their signatures position by position, count the number of equal values, and divide by k:

             h1     h2     h3     h4
A signature  0.07   0.15   0.09   0.29
B signature  0.07   0.27   0.09   0.12
equal        ✓             ✓
             → 2 of 4 = 0.5

The estimated similarity (0.5) is different from the actual value (2 shared items / 5 distinct items = 0.4). To get a more accurate estimate, k is usually much larger than in this example.

One permutation hashing18 hashes every item once, with a single hash function, and splits the range of hash values into k equal buckets. Each bucket keeps the smallest hash value among its items. Here are the same sets with k=4, using h1 from above:

bucket       0            1            2            3
range        0.00–0.25    0.25–0.50    0.50–0.75    0.75–1.00

A items      fox 0.07     dog 0.48                  owl 0.90
             cat 0.21
B items      fox 0.07     dog 0.48     emu 0.63

A minimums   0.07         0.48         ·            0.90
B minimums   0.07         0.48         0.63         ·

Each bucket works like a separate MinHash over the items in its range. So the bucket minimums form a signature, and comparing two signatures works the same way. But there is a catch: when a set isn't much larger than k, some buckets end up empty (shown as · above), so there's nothing to compare in them.

Optimal densification19 solves this by filling each empty bucket with the value from another bucket in the same set. Each empty bucket tries other buckets in a pseudo-random order and copies the value of the first non-empty one:

bucket       0         1         2         3
A minimums   0.07      0.48      ·         0.90
B minimums   0.07      0.48      0.63      ·

A signature  0.07      0.48      0.90 (3)  0.90
B signature  0.07      0.48      0.63  │   0.07 (0)
equal        ✓         ✓               │         │
             → 2 of 4 = 0.5            │         │
                                       │         │
             which bucket the value was copied from

This order depends only on the empty bucket's position, so two similar sets tend to fill empty spots with the same values. This makes the estimate work for sets of any size, with about the same error as classic MinHash.

Unsure keeps the k bucket minimums in the sketch. Add and Merge use the original buckets. Densification only happens in Signature, and it makes a copy of the buckets without modifying the sketch.

Each item is hashed once with 64-bit wyhash. Multiplying the hash by k once gives both the bucket and the value to store:

┌─────────────────┬─────────────────┬─────────────────┐
│ high 64 bits:   │ next 32 bits:   │ rest:           │
│ bucket in [0,k) │ value           │ unused          │
└─────────────────┴─────────────────┴─────────────────┘
127              64                32                 0

Densification fills empty buckets in a coordinated way, spreading the copies evenly across the non-empty buckets. This keeps the error close to classic MinHash, and makes densification fast even for small sets.

Benchmarks

Here's an excerpt from the full benchmarks20, comparing unsure to dgryski21 (classic MinHash) (ns/op, lower is better):

Operationkunsuredgryski
Add64530
2565115
10245358
Similarity642524
256104103
1024378376

RMSE of the similarity estimate at k=256 and J=0.5 (lower is better):

Distinct itemsunsuredgryski
2562.89%3.07%
1,0242.84%3.12%
4,0962.99%3.09%
16,3843.11%3.07%
Memory1.0 KB2.0 KB

Unsure adds items 6–70× faster than dgryski, compares signatures at the same speed, has roughly the same accuracy, and uses half the memory.

  1. Classic MinHash paper by Andrei Broder, 1997. ↩︎

  2. One permutation hashing by Ping Li et al., 2012. ↩︎

  3. Optimal densification paper by Anshumali Shrivastava, 2017. ↩︎

  4. MinHash benchmarks. ↩︎

  5. dgryski/go-minhash by Damian Gryski. ↩︎

Wrapping up

Bloom filter and HyperLogLog are everyone's favorites, but they're not the only useful probabilistic data structures out there. In some situations, you might find these helpful:

  • Binary fuse filter is a more compact alternative to a Bloom filter when you know all the items in advance.
  • UltraLogLog is a more compact (but slower) alternative to HyperLogLog.
  • Log-linear histogram is a much more accurate alternative to t-digest (with a variable size).
  • MinHash compares large sets for similarity using a tiny fixed-size signature.

To use them in Go, try the nalgeon/unsure package:

go get github.com/nalgeon/unsure

★ Subscribe to keep up with new posts.