MinHash-rs

一个尝试在内存使用上节省的MinHash的Rust实现。

什么是MinHash？

MinHash是一种用于估计两个集合之间相似性的概率数据结构。它基于以下观察：如果我们对两个集合的对象进行哈希处理，则这两个集合的哈希值相同的概率等于这两个集合的Jaccard相似度。

它是如何工作的？

MinHash通过哈希处理集合的元素，并跟踪每个哈希函数的最小哈希值来工作。两个集合的最小哈希值相同的概率等于两个集合之间的Jaccard相似度。通过使用多个哈希函数，我们可以通过平均两个集合的最小哈希值相同的概率来估计两个集合之间的Jaccard相似度。

使用此软件包

像往常一样，只需将以下内容添加到您的 Cargo.toml 文件中，尽管在尝试MinHash之前，请先检查下面的基准测试结果。

[dependencies]
minhash-rs = "0.1.0"

实现此版本的原因

我想测试MinHash在估计两个集合之间的Jaccard相似度方面的效果如何，以及它与HyperLogLog等方法的比较效果如何。我找到的实现比数据结构本身需要的内存更多，我想在相同内存使用量下比较MinHash与其他方法的性能。此外，通常这些方法没有进行任何形式的优化，我想尽可能地公平地比较MinHash与我相当优化的HyperLogLog实现。我已经在许多不同的宇宙大小上对MinHash进行了基准测试，您可以在这里找到Jupyter Notebook。

您可以在 测试文件夹 中找到原始基准测试结果，压缩的CSV文件。我将持续添加数据点以确保准确性，但结果似乎已经非常明确。

经过几天的基准测试，结果似乎已经出来，MinHash似乎并不比在可比较的内存需求下HyperLogLog更优越。

这是最全面的可视化（在Jupyter Notebook中找到更多），其中x轴是内存大小（对数刻度），y轴是估计Jaccard相似度的均方误差（MSE）与估计Jaccard相似度所需时间的乘积，也使用对数刻度。数值越低越好。