HyperBitBit

Robert Sedgewick在AC11-Cardinality.pdf中提出的HyperBitBit算法的原生Rust实现

特性

• HyperBitBit，对于N < 2^64
• 使用128 + 8位的空间
• 对于大N，估计的基数在10%以内或实际值。

考虑到HyperLogLog变体在生产使用中的使用，因为这个数据结构已经被广泛研究、可合并且更准确。HyperBitBit是极其便宜且快速的替代方案，但牺牲了精度。

使用方法

此crate位于crates.io，可以通过将hyperbitbit添加到项目的Cargo.toml中的依赖项来使用。

[dependencies]
hyperbitbit = "0.0.1-alpha.1"

如果您想使用serde支持，请按以下方式包含功能

[dependencies]
hyperbitbit = { version = "0.0.1-alpha.1", features = ["serde_support"] }

将此添加到crate根目录

extern crate hyperbitbit;

示例

创建一个HyperBitBit，添加更多数据并估计基数

use hyperbitbit::HyperBitBit;
use rand::distributions::Alphanumeric;
use rand::prelude::*;
use std::collections::HashSet;

fn main() {
    // create hbb for cardinality estimation
    let mut hbb = HyperBitBit::new();
    // hash set to measure exact cardinality
    let mut items = HashSet::new();
    // fixed seed for RNG for reproducibly results
    let mut rng = StdRng::seed_from_u64(42);
    // put bunch of random strings on hbb and hash set for comparison
    let maxn = 10000;
    for _ in 1..maxn {
        let s = (&mut rng).sample_iter(&Alphanumeric).take(4).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!("Actuals cardinality:   {:?}", expected);
    println!("Estimated cardinality: {:?}", hbb.cardinality());
    println!("Error % cardinality:   {:.2}", rel);
}

许可证

根据Apache License，版本2.0许可