局部敏感哈希 (LSH) 如何工作？
How Locality Sensitive Hashing (LSH) works?
我已经读过 this question，但不幸的是它没有帮助。
我不明白的是，一旦我们了解了将哪个存储桶分配给我们的高维 space 查询向量 q，我们会做什么：假设使用我们的一组局部敏感族函数 h_1,h_2,...,h_n 我们已经将 q 翻译成低维（n 维）哈希码 c.
然后 c 是分配给 q 的桶的索引，并且（希望）也分配了最近的邻居，假设有 100 个向量。
现在，为了找到 q 的 NN，我们要做的就是计算 q 和 之间的距离，只有 这 100 个向量，那是对的吗？所以 c 的使用只是为了索引（它只是用来决定将 q 分配给哪个桶），对吧？
另一种解决方案，如 this 调查（第 2.2 节）中所述，"hash table lookup"（先前描述的方法）的替代方法是 "fast distance approximation"，因此我们进行了详尽的研究，其中我们计算 c 和生成的哈希码之间相对于数据集中每个元素的距离。这应该很快，因为哈希码是低维 space 并且距离应该可以更快地计算（例如，如果哈希码 space 是二进制的，那么我们可以使用用于快速计算两个哈希码之间的汉明距离的 XOR 运算符）。
现在，我想知道的是：这两种方法的advantages/disadvantages是什么？为什么我应该使用一种方法而不是另一种方法？
第一个描述的方法解释了近似最近邻搜索。是的，您只需检查容器中的其他 100 个项目即可获得最佳性能 c，但您在其他相邻存储桶中遗漏好的候选对象的风险更高。
lat/lon 坐标的简单散列方案是 Geohash。您可以通过查看同一 Geohash 块中的项目来找到最近的商店，但在网格边界附近可能会出现不准确的结果。
可以找到快速距离近似的一个示例 here, it finds image matches with sufficiently small Hamming distance (utilizing pHash)。由于哈希只有 64 位长，笔记本电脑 GPU 每秒可以进行 7 亿次比较。请注意，所有图像都经过检查，没有使用索引或哈希数据结构。这样你就可以保证获得所有匹配项（在 pHash space 中）。
我已经读过 this question，但不幸的是它没有帮助。
我不明白的是，一旦我们了解了将哪个存储桶分配给我们的高维 space 查询向量 q，我们会做什么：假设使用我们的一组局部敏感族函数 h_1,h_2,...,h_n 我们已经将 q 翻译成低维（n 维）哈希码 c.
然后 c 是分配给 q 的桶的索引，并且（希望）也分配了最近的邻居，假设有 100 个向量。
现在，为了找到 q 的 NN，我们要做的就是计算 q 和 之间的距离，只有 这 100 个向量，那是对的吗？所以 c 的使用只是为了索引（它只是用来决定将 q 分配给哪个桶），对吧？
另一种解决方案，如 this 调查（第 2.2 节）中所述，"hash table lookup"（先前描述的方法）的替代方法是 "fast distance approximation"，因此我们进行了详尽的研究，其中我们计算 c 和生成的哈希码之间相对于数据集中每个元素的距离。这应该很快，因为哈希码是低维 space 并且距离应该可以更快地计算（例如，如果哈希码 space 是二进制的，那么我们可以使用用于快速计算两个哈希码之间的汉明距离的 XOR 运算符）。
现在，我想知道的是：这两种方法的advantages/disadvantages是什么？为什么我应该使用一种方法而不是另一种方法？
第一个描述的方法解释了近似最近邻搜索。是的，您只需检查容器中的其他 100 个项目即可获得最佳性能 c，但您在其他相邻存储桶中遗漏好的候选对象的风险更高。
lat/lon 坐标的简单散列方案是 Geohash。您可以通过查看同一 Geohash 块中的项目来找到最近的商店，但在网格边界附近可能会出现不准确的结果。
可以找到快速距离近似的一个示例 here, it finds image matches with sufficiently small Hamming distance (utilizing pHash)。由于哈希只有 64 位长，笔记本电脑 GPU 每秒可以进行 7 亿次比较。请注意，所有图像都经过检查，没有使用索引或哈希数据结构。这样你就可以保证获得所有匹配项（在 pHash space 中）。