近似计算

近似计算 "是一种计算技术，它返回一个可能不准确的结果，而不是一个保证准确的结果，"它"可以在性能和能源方面提供不成比例的收益，同时仍然达到可接受的结果精度。"

这个库是几个用 Rust 编写的近似计算算法的集合。目标是

• 易用性。为了最大程度地采用，应该非常容易使用 AC 算法，而无需付出太多努力。
• 并行化。在可能的情况下，算法应该能够并行化（即核心算法的 map-reduce）。这包括数据集的序列化。
• 常见依赖。最小化依赖链，以减少构建时间和二进制大小。

注意 我没有编写这些算法中的任何一个——它们都是由其他有才华的 Rustaceans 实现的，相关仓库链接如下。然而，我已经添加了一些功能（序列化/反序列化、公开新的初始化函数等），并且我实现了从 C# 到 Rust 的版本。所有源代码都使用 MIT 许可协议。

使用

要在你的 Cargo.toml 中使用 probably

probably = "0.2.0"

要包含数据结构的序列化，包括 with_serde 功能

probably = { version = "0.2.0", features = ["with_serde"] }

这个库中实现和在路线图上的算法可以分为几个类别

基数/频率

这些算法在某个近似可接受的误差内估计集合中的项目数量。

• HyperLogLog (HLL) -- 从 rust-hyperloglog 实现
• Count-min sketch -- 从 rust-count-min-sketch 实现，用作事件频率表

成员资格

这些算法确定项目 n 是否存在于集合 N 中，确保没有假阴性，但会牺牲一些假阳性。

• Bloom Filter -- 从 bloom_filter 实现
• Quotient filter -- 与 Bloom Filter 类似，但可以更有效地合并和调整大小。比 BF 多占用 10-25% 的空间。
  • MQF论文，“一种紧凑的散列表，可以高效存储具有偏斜分布的k-mer”
  • MQF使用C++实现
• 布谷鸟过滤器 -- 从rust-cuckoofilter实现。类似于布隆过滤器，但可以删除项。比BF占用更少的空间。

分位数估算器

• 分段抛物线分位数估算器 -- 从perfolizer C#翻译
  • 其他 perfolizer 估算器
• Greenwald-Khanna -- 从postmates/quantiles实现
• Misra-Gries -- 也来自 postmates/quantiles
• 直方图 -- 也来自 postmates/quantiles

其他

• MinHash用于估计两个集合的相似度

阅读材料

• 概率数据结构