LSH的桶数

Question

在LSH中，您将hash slices of the documents放入桶中。这样做的想法是，这些落入同一个桶中的文档可能是相似的，因此可能是最近的邻居。

对于40.000个文档来说，桶的数量有什么好的价值(差不多)？

我现在把它叫做：number_of_buckets = 40.000/4，但是我觉得它可以减少更多。

有什么想法吗？

亲属：How to hash vectors into buckets in Locality Sensitive Hashing (using jaccard distance)?

Answer 1

我认为至少应该是n。如果小于这一点，假设是n/2，您可以确保每个文档平均至少有一个可能的类似文档，这是由于碰撞。因此，计算相似性时的复杂性至少是O(n)。

另一方面，您将必须通过桶至少K倍，所以是O(K*B)，是B您的桶。我认为后者更快，因为它只是迭代数据结构(即某种字典)，并计算每个桶上散列的文档数。