probabilistic-collections-rs

probabilistic-collections 包含了使用近似方法来提高运行时间或内存使用，但引入一定量错误的集合的各种实现。错误可以在一定阈值下进行控制，这使得这些数据结构对于大数据和流式应用极为有用。

实现了以下类型的集合：

• 集合中的近似成员资格：BloomFilter、PartitionedBloomFilter、CuckooFilter、QuotientFilter
• 可扩展集合中的近似成员资格：ScalableBloomFilter、ScalableCuckooFilter
• 流中的近似成员资格：BSBloomFilter、BSSDBloomFilter、RLBSBloomFilter
• 近似项目计数：CountMinSketch
• 近似不同项目计数：HyperLogLog
• 集合相似度：MinHash、SimHash

用法

将此内容添加到您的 Cargo.toml

[dependencies]
probabilistic-collections = "*"

如果您需要 serde 支持，请包含 serde 功能

[dependencies]
probabilistic-collections = { version = "*", features = ["serde"] }

如果您使用 Rust 2015，请将此内容添加到您的包根目录

extern crate probabilistic_collections;

注意事项

如果您使用此crate创建要在不同平台间使用的集合，您必须小心不要使用类型为[T]的键。Rust标准库中针对[T]实现的Hash首先对切片的长度进行散列，然后是对切片内容的散列。长度是平台特定的，因为它属于类型usize。因此，具有类型为[T]的键的集合，在跨平台使用时将会有意外的结果。例如，如果您在i686编译的代码中生成和序列化一个键为类型[u8]的BloomFilter，在x86_64编译的代码上反序列化时，过滤器将不会得到正确的结果。

建议的解决方案是定义一个包装结构，该结构围绕一个[T]定义，并具有只散列切片内容的Hash实现。

更新日志

有关详细信息，请参阅更新日志。

参考资料

• 基于高级Bloom过滤器的流中高效近似数据去重算法

  Bera, Suman K.，Sourav Dutta，Ankur Narang，和Souvik Bhattacherjee. 2012. "基于高级Bloom过滤器的流中高效近似数据去重算法." CoRR abs/1212.3964. http://arxiv.org/abs/1212.3964.

• 改进的数据流摘要：Count-Min Sketch及其应用

  Cormode, Graham，和S. Muthukrishnan. 2005. "改进的数据流摘要：Count-Min Sketch及其应用." J. Algorithms 55 (1). Duluth, MN, USA: Academic Press, Inc.: 58--75. https://doi.org/10.1016/j.jalgor.2003.12.001.

• Cuckoo Filter：比Bloom更优

  Fan, Bin，Dave G. Andersen，Michael Kaminsky，和Michael D. Mitzenmacher. 2014. "Cuckoo Filter：比Bloom更优." In 第10届ACM国际流式网络实验与技术研究会议论文集，75--88. CoNEXT '14. New York, NY, USA: ACM. https://doi.org/10.1145/2674005.2674994.

• 不要浪费：如何在闪存上缓存您的哈希

  Bender, Michael A.，Martin Farach-Colton，Rob Johnson，Russell Kraner，Bradley C. Kuszmaul，Dzejla Medjedovic，Pablo Montes，Pradeep Shetty，Richard P. Spillane，和Erez Zadok. 2012. "不要浪费：如何在闪存上缓存您的哈希." Proc. VLDB Endow. 5 (11). VLDB Endowment: 1627--37. https://doi.org/10.14778/2350229.2350275.

• HyperLogLog的实际应用：一种顶级基数估计算法的算法工程

  Heule, Stefan，Marc Nunkesser，和Alexander Hall. 2013. "HyperLogLog的实际应用：一种顶级基数估计算法的算法工程." In 第16届国际扩展数据库技术会议论文集，683--92. EDBT '13. New York, NY, USA: ACM. https://doi.org/10.1145/2452376.2452456.

• HyperLogLog：一种近乎最优的基数估计算法的分析

  Flajolet, Philippe，Éric Fusy，Olivier Gandouet，和Frédéric Meunier. 2007. "HyperLogLog：一种近乎最优的基数估计算法的分析." In 第2007年国际算法分析会议论文集.

• 减少哈希，保持性能：构建更好的Bloom过滤器

  基尔希、亚当和迈克尔·米滕马赫。2008. "更少的哈希，相同性能：构建更好的布隆过滤器。" 随机结构算法 33 (2)。纽约，纽约，美国：约翰·威利父子有限公司：187--218. https://doi.org/10.1002/rsa.v33:2.

• Min-wise独立排列（扩展摘要）

  布罗德、安德烈·Z.、摩西·查里克、艾伦·M. 弗里斯和迈克尔·米滕马赫。1998. "Min-Wise独立排列（扩展摘要）。" 在 第三十届ACM理论计算年会论文集，327--36。STOC '98。纽约，纽约，美国：ACM。 https://doi.org/10.1145/276698.276781.

• 基于simhash的概率近重复检测

  苏德、萨丹和德米特里·洛古诺夫。2011. "基于simhash的概率近重复检测。" 在 第20届ACM国际信息与知识管理会议论文集，1117--26。CIKM '11。纽约，纽约，美国：ACM。 https://doi.org/10.1145/2063576.2063737.

• 可扩展的布隆过滤器

  阿尔梅达、保罗·塞尔吉奥、卡洛斯·巴奎罗、努诺·普雷古萨和戴维·哈奇森。2007. "可扩展的布隆过滤器。" 信息处理快报 101 (6)。阿姆斯特丹，荷兰，荷兰：爱思唯尔诺顿出版社：255--61. https://doi.org/10.1016/j.ipl.2006.10.007.

许可证

probabilistic-collections-rs 根据 MIT 许可证或 Apache 许可证（版本 2.0）条款双许可。

有关详细信息，请参阅 LICENSE-APACHE 和 LICENSE-MIT。