2

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

我不明白的是，一旦我们了解了哪个桶分配给我们的高维空间查询向量，我们会做什么q：假设使用我们的一组位置敏感的族函数h_1,h_2,...,h_n，我们已经转换q为低维（n维度）哈希码c。

然后c是分配给的桶的索引，q以及（希望）分配给它的最近邻居的位置，假设有 100 个向量。

现在，为了找到 NN，我们要做的是计算这100 个向量之间的q距离，对吗？所以使用仅用于索引（它仅用于决定分配给哪个存储桶），对吗？qcq

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

现在，我想知道的是：这两种方法的优点/缺点是什么？为什么我应该使用一种方法而不是另一种方法？

4

1 回答 1

2

第一种描述的方法解释了近似最近邻搜索。是的，您只需检查 bin 中的这 100 个其他项目即可获得最佳性能c，但您在其他相邻存储桶中错过好的候选人的风险更高。

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

可以在此处找到快速距离近似的一个示例，它找到具有足够小的汉明距离的图像匹配（利用pHash）。由于哈希只有 64 位长，笔记本电脑 GPU 每秒可以进行 7 亿次比较。请注意，检查所有图像，不使用索引或散列数据结构。这样，您就可以保证获得所有匹配项（在 pHash 空间中）。

于 2016-06-14T07:50:55.067 回答