Crate exaloglog 

ExaLogLog: space-efficient approximate distinct counting.

Implementation of the ExaLogLog (ELL) algorithm by Otmar Ertl, “ExaLogLog: Space-Efficient and Practical Approximate Distinct Counting up to the Exa-Scale”, arXiv:2402.13726 (2024).

Compared to HyperLogLog with 6-bit registers, ExaLogLog achieves the same estimation error with ~43% less memory (ExaLogLog, packed d=20) or ~41% less memory with 32-bit aligned registers (ExaLogLogFast, d=24) which are easier to access concurrently.

Both variants:

• support distinct counts up to the exa-scale (10¹⁹+);
• are mergeable, idempotent, and reducible;
• have constant-time inserts independent of p;
• implement martingale (HIP) and maximum-likelihood estimators.

Example

use exaloglog::ExaLogLog;

let mut sketch = ExaLogLog::new(12);
for i in 0..100_000u64 {
    sketch.add(&i);
}
let estimate = sketch.estimate();
assert!((estimate - 100_000.0).abs() / 100_000.0 < 0.05);

Structs

ExaLogLog

Packed 28-bit ExaLogLog. See module docs.

ExaLogLogFast

32-bit aligned ExaLogLog. See module docs.

Enums

DeserializeError

Error returned when deserializing a byte slice into an ExaLogLog sketch.

MergeError

Error returned when two sketches cannot be merged.

Constants

MAX_P

Maximum supported precision parameter p.

MIN_P

Minimum supported precision parameter p.

T

t parameter of the approximated update value distribution. Fixed at 2 in this build — both ExaLogLog (d=20) and ExaLogLogFast (d=24) use it, and it’s the configuration the paper recommends in practice.