本地敏感散列(LSH)是如何工作的？

Question

我已经读过这个问题了，但不幸的是，它没有帮助。

我不明白的是，一旦我们理解了给高维空间查询向量q分配哪个桶，我们会做什么:假设使用我们的一组局部性敏感的家族函数h_1,h_2,...,h_n，我们已经将q转换为一个低维(n维度)哈希代码c。

然后，c是q分配给的桶的索引，并且(希望)分配给它最近的邻居的位置(希望如此)，假设有100个向量。

现在，为了找到q的NN，我们要计算q和之间的距离，只有这100个向量，对吗?所以c只用于索引(只用于决定哪个桶分配q‘)，对吗？

另一种解决方案，如这调查(第2.2节)所述，“哈希表查找”(前面描述的方法)的替代方案是“快速距离近似”，因此我们进行了详尽的研究，计算出相对于数据集中的每个元素的c和生成的哈希码之间的距离。这应该是快速的，因为哈希码是在一个低维空间，而且距离应该更快计算(例如，如果哈希码空间是二进制的，那么我们可以使用XOR运算符来快速计算两个哈希码之间的汉明距离)。

现在，我想知道的是:这两种方法的优缺点是什么？为什么我要用一种方法而不是另一种方法呢？

Answer 1

第一个描述的方法解释了一个近似的最近邻搜索。是的，只要检查bin c中的其他100个项目，就可以获得最好的性能，但是在其他邻近的桶中丢失优秀候选人的风险更高。

lat/lon坐标的一个简单的散列方案是Geo散列。您可以通过查看同一Geo散列块中的项目来找到最近的商店，但在网格边界附近可能会有不准确的结果。

快速距离近似的一个例子是这里，它可以找到足够小的Hamming距离的图像匹配(利用pHash)。由于散列只有64位长，所以一台膝上型计算机GPU每秒可以进行7亿次比较。请注意，将检查所有图像，不使用索引或散列数据结构。这样，您的年龄保证得到所有匹配(在pHash空间)。