几何计数过滤器

此crate实现了使用几何过滤器解决唯一计数问题的概率数据结构。实现了两种变体，它们在将新元素添加到过滤器的方式上有所不同。

• GeoDiffCount通过对称差分添加元素。元素可以添加和后来删除。支持估计两个集合的对称差分的大小，其精度与估计的大小有关，而与原始集合的并集无关。
• GeoDistinctCount通过并集添加元素。元素可以添加，重复元素将被忽略。可以估计两个集合的并集，具有与估计大小相关的精度。它具有与HyperLogLog、MinHash等相关过滤器的类似属性，但占用的空间更少。

使用方法

将其添加到您的Cargo.toml

[dependencies]
geo_filters = "0.1"

使用默认配置进行唯一计数的简单示例

use geo_filters::distinct_count::GeoDistinctCount13;
use geo_filters::Count;

let mut c1 = GeoDistinctCount13::default();
c1.push(1);
c1.push(2);

let mut c2 = GeoDistinctCount13::default();
c2.push(2);
c2.push(3);

let estimated_size = c1.size_with_sketch(&c2);
assert!(estimated_size >= 3.0_f32 * 0.9 &&
        estimated_size <= 3.0_f32 * 1.1);

背景

使用几何过滤器估计集合大小的想法起源于GitHub新代码搜索项目的开发 ^1。我们正在寻找一种高效的方法来近似不同仓库中文件集合之间的相似性。Alexander Neubeck，在Pavel Avgustinov的仔细审查下，开发了成为几何差分计数过滤器的数学。该过滤器允许我们根据仓库相似性计算近似的最小生成树，这为我们提供了仓库处理计划，减少了重复工作并增加了数据共享。这是新代码搜索在生产中的索引管道的重要部分 ^2。

对于这个开源库，Alexander Neubeck 相比于我们的原始实现简化了数学计算，Hendrik van Antwerpen 优化了代码和评估实验。

与 HLL++ 的比较

大多数项目依赖于 HLL++，这是 HyperLogLog 算法的继任者，它在内存和CPU使用方面非常高效。本库中提出的 GeoDistinctCount 解决方案通过大型集合减少了25%的内存消耗，对于更小的集合来说甚至更多，同时保持更新速度快。与 HLL++ 相比，提出的算法对所有集合大小使用相同的表示，因此在概念上也更简单。当最重要的桶ID使用可变增量编码时，仅需要50%的 HLL++ 内存即可达到相同的精度。

为了简单起见，我们将我们的 GeoDistinctCount 实现与一个现有的、未针对速度优化的 Rust HLL++ 端口进行了基准测试。我们的实现对于所有大小至少与 HLL++ 端口一样快。GeoDistinctCount 解决方案只需计算占用桶的数量和第一个桶的偏移量。这两个数字在增量更新期间都会被跟踪，这样就可以在常数时间内计算出不同的计数。

评估

预定义过滤配置的准确性和性能评估包含在仓库中

• 准确性结果
• 性能结果

预定义配置应该对大多数用户足够。如果您想评估自定义配置或重现这些结果，请参阅 说明。