cardinality-estimator

cardinality-estimator is a Rust crate designed to estimate the number of distinct elements in a stream or dataset in an efficient manner. This library uses HyperLogLog++ with an optimized low memory footprint and high accuracy approach, suitable for large-scale data analysis tasks. We're using cardinality-estimator for large-scale machine learning, computing cardinality features across multiple dimensions of the request.

Overview

Our cardinality-estimator is highly efficient in terms of memory usage, latency, and accuracy. This is achieved by leveraging a combination of unique data structure design, efficient algorithms, and HyperLogLog++ for high cardinality ranges.

Getting Started

To use cardinality-estimator, add it to your Cargo.toml under [dependencies]:

[dependencies]
cardinality-estimator = "1.0.0"

Then, import cardinality-estimator in your Rust program:

use cardinality_estimator::CardinalityEstimator;

let mut estimator = CardinalityEstimator::<12, 6>::new();
estimator.insert("test");
let estimate = estimator.estimate();

println!("estimate = {}", estimate);

Please refer to our examples and benchmarks in the repository for more complex scenarios.

Low memory footprint

The cardinality-estimator achieves low memory footprint by leveraging an efficient data storage format. The data is stored in three different representations - Small, Array, and HyperLogLog - depending on the cardinality range. For instance, for a cardinality of 0 to 2, only 8 bytes of stack memory and 0 bytes of heap memory are used.

Low latency

The crate offers low latency by using auto-vectorization for slice operations via compiler hints to use SIMD instructions. The number of zero registers and registers' harmonic sum are stored and updated dynamically as more data is inserted, resulting in fast estimate operations.

High accuracy

The cardinality-estimator achieves high accuracy by using precise counting for small cardinality ranges and HyperLogLog++ with LogLog-Beta bias correction for larger ranges. This provides expected error rates as low as 0.02% for large cardinalities.

Benchmarks

To run benchmarks you first need to install cargo-criterion binary:

cargo install cargo-criterion

Then benchmarks with output format JSON to save results for further analysis:

make bench

We've benchmarked cardinality-estimator against several other crates in the ecosystem:

• hyperloglog
• hyperloglogplus
• amadeus-streaming
• probabilistic-collections

Please note, that hyperloglog and probabilistic-collections crates have bug in calculation of precision p based on provided probability:

• incorrect formula: p = (1.04 / error_probability).powi(2).ln().ceil() as usize;
• corrected formula: p = (1.04 / error_probability).powi(2).log2().ceil() as usize;

We're continuously working to make cardinality-estimator the fastest, lightest, and most accurate tool for cardinality estimation in Rust.

Benchmarks presented below are executed on Linux laptop with 13th Gen Intel(R) Core(TM) i7-13800H processor and compiler flags set to RUSTFLAGS=-C target-cpu=native.

Memory usage

Table below compares memory usage of different cardinality estimators. The number in each cell represents stack memory bytes / heap memory bytes / heap memory blocks at each measured cardinality.

Our cardinality-estimator achieves the lowest stack and heap memory allocations across all different cardinalities.

Note, that hyperloglogplus implementation has particularly high memory usage especially for cardinalities above 256.

Insert performance

Table below represents insert time in nanoseconds per element.

Our cardinality-estimator demonstrates the lowest insert time for most of the cardinalities.

Estimate performance

Table below represents estimate time in nanoseconds per call.

Our cardinality-estimator shows the lowest estimate time for most of the cardinalities, especially smaller cardinalities up to 128.

Note, that amadeus-streaming implementation is also quite effective at estimate operation, however it has higher memory usage as indicated by table above. Implementations probabilistic-collections, hyperloglogplus and hyperloglogplus have much higher estimate time, especially for higher cardinalities.

Error rate

Table below represents average absolute relative error across 100 runs of estimator on random elements at given cardinality.

Our cardinality-estimator performs on par well with amadeus-streaming and hyperloglog estimators, but has especially smaller low error rate for cardinalities up to 128.

Note, that probabilistic-collections implementation seems to have bug in its estimation operation for cardinalities >=32768.