cardinality-estimator

cardinality-estimator 是一个Rust crate，旨在以高效的方式估计流或数据集中不同元素的数量。该库使用HyperLogLog++，具有优化的低内存占用和高度精确的方法，适用于大规模数据分析任务。我们在大规模机器学习中使用 cardinality-estimator，在请求的多个维度上计算基数特征。

概述

我们的 cardinality-estimator 在内存使用、延迟和精度方面都非常高效。这是通过利用独特的数据结构设计、高效算法以及HyperLogLog++对高基数范围的优化来实现的。

入门指南

要使用 cardinality-estimator，请将其添加到您的 Cargo.toml 中的 [dependencies]

[dependencies]
cardinality-estimator = "1.0.0"

然后，在您的Rust程序中导入 cardinality-estimator

use cardinality_estimator::CardinalityEstimator;

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

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

请参阅我们仓库中的 示例 和 基准测试，了解更多复杂场景。

低内存占用

cardinality-estimator 通过利用高效的数据存储格式实现低内存占用。数据以三种不同的表示形式存储 - Small、Array 和 HyperLogLog，具体取决于基数范围。例如，对于基数为0到2的情况，只使用 8字节 的堆栈内存和0字节的堆内存。

低延迟

该crate通过使用编译器提示进行自动向量化切片操作，实现低延迟。随着更多数据的插入，动态存储和更新零寄存器和寄存器谐波和，从而实现快速的估计操作。

高精度

通过为小基数范围使用精确计数以及为较大范围使用带有LogLog-Beta偏差校正的HyperLogLog++，基数估计器实现了高精度。这为大型基数提供了低至0.02%的预期误差率。

基准测试

要运行基准测试，您首先需要安装 cargo-criterion 二进制文件

cargo install cargo-criterion

然后以 JSON 格式输出基准测试结果以供进一步分析

make bench

我们已经将基数估计器与其他几个生态系统中的 crate 进行了基准测试

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

请注意，hyperloglog 和 probabilistic-collections crate 中存在基于提供的 probability 计算精度 p 的错误

• 错误的公式：p = (1.04 / error_probability).powi(2).ln().ceil() as usize;
• 正确的公式：p = (1.04 / error_probability).powi(2).log2().ceil() as usize;

我们正在努力使 cardinality-estimator 成为 Rust 中最快的、最轻量级的和最精确的基数估计工具。

以下基准测试是在 Linux 笔记本电脑上执行的，使用 13th Gen Intel(R) Core(TM) i7-13800H 处理器，并将编译器标志设置为 RUSTFLAGS=-C target-cpu=native。

内存使用情况

下表比较了不同基数估计器的内存使用情况。每个单元格中的数字表示在每次测量的基数下 栈内存字节 / 堆内存字节 / 堆内存块。

我们的 cardinality-estimator 在所有不同的基数下都实现了最低的栈和堆内存分配。

请注意，hyperloglogplus 实现的内存使用量尤其高，特别是对于基数大于 256 的情况。

插入性能

下表表示每个元素的插入时间（纳秒）。

我们的 cardinality-estimator 在大多数基数下都表现出最低的插入时间。

估计性能

下表表示每次调用的估计时间（纳秒）。

我们的 cardinality-estimator 在大多数基数下，特别是 128 以下的较小基数中，都显示了最低的估计时间。

请注意，amadeus-streaming 的实现对于估计操作也非常有效，然而，如上表所示，它的内存使用量更高。实现 probabilistic-collections、hyperloglogplus 和 hyperloglogplus 的估计时间要高得多，尤其是在高基数情况下。

错误率

下表展示了在给定基数下，估计器在随机元素上运行100次后的平均绝对相对误差。

我们的 cardinality-estimator 在性能上与 amadeus-streaming 和 hyperloglog 估计器相当，但在基数高达128时，具有特别小的低错误率。

请注意，probabilistic-collections 实现在基数 >=32768 时的估计操作中似乎存在错误。