A native rust implementation of a HyperBitBit algorithm introduced by by Robert Sedgewick in AC11-Cardinality.pdf
- HyperBitBit, for N < 2^64
- Uses 128 + 8 bit of space
- Estimated cardinality withing 10% or actuals for large N.
Consider HyperLogLog variants for productions usage, sine this data structure extensively studied, merge able and more accurate. HyperBitBit is extremely cheap and fast alternative in expense of accuracy.
This crate is on crates.io and
can be used by adding hyperbitbit
to the dependencies in your
project's Cargo.toml
.
[dependencies]
hyperbitbit = "0.0.1-alpha.1"
If you want serde support, include the feature like this:
[dependencies]
hyperbitbit = { version = "0.0.1-alpha.1", features = ["serde_support"] }
add this to your crate root:
extern crate hyperbitbit;
Create a HyperBitBit, add more data and estimate cardinality
use hyperbitbit::HyperBitBit;
use rand::Rng;
use rand::SeedableRng;
use rand::distributions::Alphanumeric;
use rand_isaac::Isaac64Rng;
use std::collections::HashSet;
fn main() {
let mut hbb = HyperBitBit::new();
let mut items = HashSet::new();
let mut rng = Isaac64Rng::seed_from_u64(42);
let maxn = 100000;
for _ in 1..maxn {
let s = (&mut rng).sample_iter(&Alphanumeric).take(3).collect::<String>();
hbb.insert(&s);
items.insert(s);
}
let expected: i64 = items.len() as i64;
let rel: f64 = (100.0 * (expected - hbb.cardinality() as i64) as f64) / (expected as f64);
println!("Cardinality: {:?}", expected);
println!("Estimated cardinality: {:?}", hbb.cardinality());
println!("Error % cardinality: {:.2}", rel);
}
Licensed under the Apache License, Version 2.0