位置敏感哈希 - 当桶为空时会发生什么？

Question

假设我已经根据一些散列集构建了一个 LSH 数据库，现在我开始查询数据库以找到近似最近的邻居。

当您计算查询点的哈希值并且相应的存储桶为空时，是否有任何指导方针？同样，假设我要找到 5 个近似最近邻，而桶中只有 4 个其他数据点？

Answer 1

我认为检索点数太少意味着您的训练数据桶太多。这当然取决于应用程序。看看LSH toolbox by Greg Shakhnarovich implementation and his README file。在这个实现中，更少的哈希函数（更小的 k）意味着更满的桶，这反过来意味着更慢的 LSH。