Crate subms_hyperloglog 

HyperLogLog cardinality estimator.

Precision p in [4, 18]. The register array is m = 2^p bytes. Hashes split into a p-bit register index (top bits) and a leading-zero count on the remaining bits. Each register stores the max observed count + 1. Estimate is the harmonic mean of 2^r over the registers, scaled by an alpha_m correction. Linear-counting kicks in at low cardinality where the raw estimator is biased.

use subms_hyperloglog::HyperLogLog;
let mut hll = HyperLogLog::new(14);
for i in 0..10_000 { hll.add(&format!("key{i}")); }
let est = hll.estimate();
assert!(est > 9_000.0 && est < 11_000.0, "10k distinct within 10%, got {est}");

Thread safety

A HyperLogLog is a single-writer structure. add, merge and clear take &mut self, so the compiler already stops two threads sharing one sketch without a lock. The fan-in pattern is a sketch per thread or shard and one merge at read time; the merge is exact, so nothing is lost by never sharing a writer. estimate takes &self and is safe to call concurrently on a sketch nobody is writing.

Full writeup, design notes and measured benchmarks: https://www.submillisecond.com/cookbook/recipes/subms-hyperloglog

Re-exports

pub use features::sparse::SparseHyperLogLog;

pub use features::union_intersect::estimate_intersect;

pub use features::union_intersect::estimate_union;

pub use features::union_intersect::intersect_error_bound;

Modules

features

Opt-in HyperLogLog feature modules. Each entry is gated by its own Cargo feature; the base HyperLogLog in lib.rs stays zero-dep.

recipe

SubMsRecipe impl. Behind the harness feature.

Structs

HyperLogLog

Enums

HllError

Every failure subms-hyperloglog can return.

Constants

FORMAT_VERSION

Format version. Bumped only on a breaking layout change.

MAGIC

Leading bytes of every buffer this codec writes.

MAX_PRECISION

Highest precision this recipe allocates for. 2^18 registers is 256 KB.

MIN_PRECISION

Lowest precision the estimator is calibrated for.

RSE_CONSTANT

Flajolet’s asymptotic relative standard error constant. Standard error is RSE_CONSTANT / sqrt(m).