algorithm - LSH : practice of solving nearest neigbors search

Question

"LSH has some huge advantages. First, it is simple. You just compute the hash for all points in your database, then make a hash table from them. To query, just compute the hash of the query point, then retrieve all points in the same bin from the hash table."

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

1. 我的第一步是计算每个向量的哈希值。距离测量重要吗？ (我想是的)。阈值重要吗？ (我想没有)。我怎样才能找到合适的散列函数？

   如果编程，我会有这样的功能:

   bytes[] getHash(Vector featureVec)

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

2. 然后我从散列中创建散列表(将散列放入容器中)。我想至少在这里阈值应该很重要。我该怎么做？

   如果编程的话，会是这样的:

   Map,Map createHashTable(Map vectorHashMap, long threshold)

   返回两个 map :Map of (hashCode, bucketId)和 Map of (bucketId, ListOfVectorIds) .

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

Answer 1

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

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

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