algorithm - LSH：解决最近邻搜索的实践

Question

“LSH 有一些巨大的优势。首先，它很简单。你只需计算数据库中所有点的哈希值，然后从中制作一个哈希表。要查询，只需计算查询点的哈希值，然后检索数据库中的所有点哈希表中的同一个 bin。”

参考另一个问题的答案，我正在寻找对 LSH 分析过程的澄清。假设我有稀疏的特征向量（二进制，大部分为 0）并且想使用余弦距离作为具有阈值 alpha 的度量，这可能会有所不同。

1. 我的第一步是计算每个向量的哈希值。距离测量重要吗？（我想是的）。门槛重要吗？（我想没有）。如何找到合适的哈希函数？

   如果编程，我将具有如下功能：

   bytes[] getHash(Vector featureVec)

   然后我会把结果放在Map(long vectorId, bytes[] hashcode) <-vectorHashMap

2. 然后我从哈希中制作哈希表（将哈希放入垃圾箱）。我想至少在这里阈值很重要。我怎样才能做到这一点？

   如果编程，它会像：

   Map,Map createHashTable(Map vectorHashMap, long threshold)

   它返回两个地图：Map of (hashCode, bucketId)和Map of (bucketId, ListOfVectorIds)。

3. 然后我可以轻松地检索以 vectorId 作为输入并以 vectorIds 列表作为输出的邻居。

Answer 1

哈希与距离度量无关。您可以通过用随机选择的向量点缀向量来获得散列的每一位。该位表示散列向量在随机向量的哪一侧（实际上是超平面）。这些位一起是一个哈希。

是的，那么您可以通过哈希值索引您的向量以便于检索。您不需要“桶 ID”——您的哈希就是您的桶。

这里唯一的问题是，并非所有最近的向量都在它散列的桶中。他们只是倾向于靠近。如果这很重要，您可能必须搜索“相似”的桶——那些只有几位不同的桶——以考虑更多的候选人并更好地找到真正最近的邻居。