5

我已经有了生成局部敏感散列的算法,但是我应该如何将它们存储起来以利用它们的特性(即相似的元素具有接近散列(具有汉明距离))?

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

我试图搜索它,但我不确定如何将我找到的任何方法应用于我的案例(如多探针方法)。如果您已经拥有哈希值,那么这些技术似乎都不是很容易插入的。是否有任何简单的示例代码?或者有什么建议?

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

4

1 回答 1

0

基于:Search in localitysensitive hashing我会这样说,在阅读了 Rounding Algorithms 中的相似性估计技术之后:

这个问题有点宽泛,所以我在这里只给出一个最小(抽象)的例子:

我们的数据集中有 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


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

于 2016-05-23T06:29:04.560 回答