LSH:求解最近邻搜索的实践

Question

To query, just compute the hash of the query point, then retrieve all points in the same bin from the hash table."

关于另一个问题的答案，我想要澄清LSH分析的过程。假设我有稀疏的特征向量(二进制，大部分为0)，并且希望使用余弦距离作为阈值α的度量，这可能会有所变化。

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

散列与距离测量无关。通过将向量与随机选择的向量点缀，就可以得到每一位哈希。位表示随机向量(真正的超平面)的哪一边是散列向量。这些位在一起是一个散列。

是的，然后根据散列值对向量进行索引，以便于检索。你不需要“桶号”--你的哈希就是你的桶。

这里唯一的问题是，并不是所有最近的向量都在它所散列的桶中。他们只是倾向于接近。如果重要的话，你可能需要搜索“类似的”桶--只有几个部分不同的桶--来考虑更多的候选人，并更好地找到真正最接近的邻居。