hll-rs

A HyperLogLog implementation in Rust, tuned for low estimation bias.

What is HyperLogLog?

HyperLogLog is a probabilistic data structure for estimating the cardinality (number of distinct elements) of a multiset. It trades exactness for memory: it can estimate cardinalities in the billions with a typical error of well under 1% using only a few kilobytes of memory.

The core idea: hash every element, and observe the maximum number of leading zeros seen in the hashes. A hash with many leading zeros is rare, so observing one suggests many distinct elements have passed through. HyperLogLog refines this intuition by splitting the stream into many registers and combining their observations with a harmonic mean, which dramatically reduces variance.

Usage

use hll_rs::HyperLogLog;

// `precision` (4..=18) trades memory for accuracy: precision 14 uses
// 2^14 one-byte registers (~16 KiB) for a typical error of ~0.8%.
let mut hll = HyperLogLog::new(14).unwrap();

for i in 0..100_000u64 {
    hll.add(&i);
}

// Estimate the number of distinct elements seen.
let estimate = hll.count();
assert!((estimate - 100_000.0).abs() / 100_000.0 < 0.01);

// Sketches of equal precision can be merged to estimate set unions.
let mut other = HyperLogLog::new(14).unwrap();
other.add("a brand new element");
hll.merge(&other).unwrap();

// Sketches round-trip through a stable, versioned byte encoding.
let bytes = hll.to_bytes();
let restored = HyperLogLog::from_bytes(&bytes).unwrap();
assert_eq!(hll, restored);

Accuracy

Cardinality is estimated with Otmar Ertl's improved raw estimator, which is continuous across the whole cardinality range.

The textbook alternative — Flajolet's original design — computes a raw harmonic-mean estimate and switches to linear counting below 2.5 * m. The raw estimator is itself biased upward for roughly 2.5 * m < n < 5 * m, and that threshold hands over to it exactly where the bias peaks. Measured over thousands of trials, that costs about +2.2% of systematic over-counting around n = 2.5 * m, with roughly three times the theoretical RMS error:

Measured across precision = 4..=18 and n/m = 0.5..=200:

• For precision >= 8, bias stays within ±0.3% at every cardinality.
• For precision 4 to 6, a residual bias of up to ~3% remains at low cardinality. This is a small-m artifact, dwarfed by the dispersion at those sizes (one standard error at precision = 4 is 26%), and it runs downward — such sketches under-count rather than over-count.
• RMS error is at or below the theoretical 1.04 / sqrt(m) throughout.

Pick a precision to fit your error budget — relative_error() reports it for a live sketch:

Hashing

Elements are hashed with a built-in xxHash64 implementation, verified against the reference implementation's canonical test vectors. Its output is fixed across releases of this crate, across Rust toolchains, and across platforms — integers are always fed to the digest in little-endian order — so sketches can be serialized, shipped, and merged elsewhere.

(The standard library's DefaultHasher is explicitly not stable across Rust releases, which makes it unsuitable for persisted sketch state.)

To use a different hash function:

use hll_rs::{HyperLogLog, Xxh64BuildHasher};

// Any `BuildHasher`, or a seeded xxHash64.
let mut hll = HyperLogLog::with_hasher(14, Xxh64BuildHasher::with_seed(0x1234)).unwrap();
hll.add("hello");

// ...or feed 64-bit hashes you computed yourself.
let mut hll = HyperLogLog::new(14).unwrap();
hll.add_hash(0xDEAD_BEEF_CAFE_F00D);

Limits

• Hashes are 64 bits wide, so distinct elements begin to collide around 2^32 (~4.3 billion) distinct values. Beyond that the sketch progressively under-counts, independently of precision.
• Registers are stored one per byte rather than bit-packed into 6 bits, trading ~25% of memory for simpler, faster code.
• Sketches are not thread-safe; wrap in a lock, or build per-thread sketches and merge them (merging is exact and lossless).

Features

The crate has no required dependencies.

Performance

Measured on the CI reference machine with cargo bench:

Development

cargo test          # run the test suite
cargo test --all-features
cargo bench         # run the benchmarks
cargo clippy        # lint
cargo fmt           # format

References

• Philippe Flajolet, Éric Fusy, Olivier Gandouet, Frédéric Meunier — HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm (2007) — the original paper
• Stefan Heule, Marc Nunkesser, Alexander Hall — HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm (2013) — Google's HLL++ refinements
• Otmar Ertl — New cardinality estimation algorithms for HyperLogLog sketches (2017) — the improved raw estimator used here
• Damn Cool Algorithms: Cardinality Estimation — an approachable introduction

License

Licensed under the MIT license (LICENSE or http://opensource.org/licenses/MIT)