LSH宾宁在飞

Question

我想使用MinHash LSH将大量文档放入类似文档的桶中(Jaccard相似性)。

问题：是否有可能在不知道其他文档的MinHash的情况下计算MinHash的桶？

据我所知，LSH“只”计算MinHashes的散列。所以这应该是可能的？

我发现一个非常混杂的实现是datasketch。在了解所有文档的MinHash之后，我可以查询与给定文档类似的LSH文档。然而，在了解其他文档之前，我看不出如何获得单个文档的桶。https://ekzhu.github.io/datasketch/index.html

Answer 1

LSH不存储整个文档，也不存储单个的minhashes。更确切地说，它是一桶“乐队”的细枝末节。

LSH是一种方法，既可以减少每个文档存储的散列数，也可以减少在使用这些散列搜索类似文档时发现的命中次数。它通过将多个最小哈希合并成一个散列来实现这一点。因此，例如，与其存储每个文档的200分钟散列，不如将它们组合成4条带，从而产生50个局部性敏感散列。

每个带的散列是使用廉价的散列函数(如FNV-1a )从其组成的最小散列中计算的。这就失去了一些信息，这就是为什么说LSH降低了数据的维数。得到的哈希是桶。

因此，在不需要了解任何其他波段或任何其他文档的情况下，计算文档中每一段最小哈希的存储桶。

使用LSH散列查找类似的文档很简单:假设您希望查找与文档A类似的文档。首先为文档A生成(例如)50个LSH散列，然后在散列字典中查找共享一个或多个这些散列的所有其他文档。他们共享的哈希越多，他们估计的jaccard相似度就越高(尽管这不是一个线性关系，就像使用普通的minhashes时一样)。

每个文档存储的总哈希数越少，估计jaccard相似性的错误越大，丢失类似文档的可能性就越大。

这是LSH的一个很好的解释。