如何挖出局部敏感的哈希？

Question

我已经有了算法来产生局部敏感的哈希值,但我应该如何利用它们来利用它们的特性(即类似的元素有近哈希值(汉明距离))？

在matlab代码中,我发现它们只是在要搜索的点的散列和数据库中的点的散列之间创建一个距离矩阵,以简化代码,同时引用一个所谓的Charikar方法来实现良好的搜索实现方法.

我试图搜索它,但我不知道如何应用我的案例我找到的任何方法(如多探针方法).如果你已经有哈希,这些技术似乎都不容易插入.有没有简单的示例代码？还是有什么建议吗？

这是我正在谈论的matlab代码页面的链接:http: //www.eecs.berkeley.edu/~kulis/klsh/klsh.htm

Answer 1

基于：搜索局部敏感哈希在阅读舍入算法中的相似性估计技术后，我会这样说：

这个问题在某种程度上很广泛，所以我将在这里给出一个最小（抽象）的例子：

我们的数据集中有 6 (= n) 个向量，d每个向量都有位。假设我们进行 2 (= N) 次随机排列。

让第一个随机排列开始！请记住，我们排列的是位，而不是向量的顺序。排列位后，它们保持顺序，例如：

v1
v5
v0
v3
v2
v4

现在查询向量到达，但它（几乎）不太可能与我们数据集中的向量（排列后）相同，因此我们不会通过执行二分搜索找到它q。

然而，我们最终会处于两个向量之间。现在我们可以想象场景是这样的（例如q位于 v0 和 v3 之间：

v1
v5
v0 <-- up pointer
   <-- q lies here
v3 <-- down pointer
v2
v4

现在我们向上或向下移动指针，寻找与 最多匹配位的 vi 向量q。假设它是 v0。

类似地，我们进行第二次排列并找到向量 vi，假设为 v4。我们现在比较第一个排列中的 v0 和 v4，看看哪一个最接近q，即哪一个具有最多等于 的位q。

但是，如果您正在寻求现成的实现，您应该在软件推荐中询问。我还会查看我链接到的论文，看看作者是否公开了代码，或者他们是否愿意在联系他们后分享代码。