“locality-sensitive-hash”的相关标签问题

0 投票

4 回答

6926 浏览

c# - 局部敏感哈希实现？

在 C/C++/Java/C# 中是否有任何相对易于理解（且易于实现）的局部敏感哈希示例？

我想了解更多关于这个概念的信息，所以想在几个文本文件上尝试一个实现，看看它是如何工作的，所以我不需要任何高性能或任何东西......只是一个哈希的例子返回相似输入的相似哈希的函数。之后我可以通过示例从中学到更多。:)

c#java c hash locality-sensitive-hash

0 投票

1 回答

1982 浏览

matlab - 如何存储局部敏感哈希？

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

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

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

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

matlab nearest-neighbor locality-sensitive-hash

0 投票

1 回答

2229 浏览

c - Hashtable 的高效实现，具有缓存感知位置属性（Locality-sensitive hashtable）

我正在尝试使用 C 数据结构（哈希表）。我没有使用任何预先构建的哈希表库（如 STL），因为我想更好地了解它的工作原理。所以在这里我创建了一个哈希表，其中包含元素列表，其中每个元素包含一个键和一个字符串元素数据（字符数组），以及字符串元素数据的长度。

我的实现工作，但在与我的一位同事讨论后，我被告知我的实现效率不高，特别是在以下情况下：我的实现不支持缓存，导致我的哈希表查找效率低下。我不是很明白他的解释。

所以我想知道，缓存感知局部性实现实际上意味着什么？

在进行查找时，如何通过使用缓存感知位置属性使我的哈希表实现变得更高效？有没有更好的方法来为此构建结构，以及组织元素的更好方法（进行查找）？

这是我到目前为止所做的：

哈希表

哈希表

主文件

c hashtable locality-sensitive-hash

0 投票

1 回答

1000 浏览

locality-sensitive-hash - 如何使用局部敏感哈希--LSHKIT

我真的需要在我的程序中使用 LSHKIT 来测量一些高维向量的相似性。有一个名为 lshkit 的 lsh 库，可以在这里找到：http://lshkit.sourceforge.net/我很困惑使用它。首先我无法构建它，所以我去了第 3.2 节“直接将 LSHKIT 源添加到您的项目”
我将所有 src 代码放在一个项目中并修复了错误但现在我不知道如何使用它和编译它用于示例数据（在 lshkit 网站中提出）

你们能帮我找出如何调用函数并查看结果吗？谢谢

locality-sensitive-hash

0 投票

3 回答

2938 浏览

java - 使 Sim Hash（局部敏感散列）算法更准确？

我有两个名称和一个地址的“记录”（基本上是 CSV 字符串）。我需要找到彼此相似的记录：基本上名称和地址部分看起来都“相似”，就好像它们是由人类解释的一样。

我使用了这篇出色的博客文章中的想法：http: //knol.google.com/k/simple-simhashing#编写了一个简单的 SimHash。如果两个或多个字符串的 SimHash 结果相同，我会将这个子集的所有记录传递给一个细粒度的匹配程序，该程序是 O(n^2)，它将集合中的每条记录与其他每条记录进行比较。

对于 SimHash 部分，我有一些参数，我可以在其中定义数据报大小（基本上是字符串上大小为 n 的滑动窗口）和用于确定 SimHash 计算需要使用多少（随机）哈希的迭代次数. 到目前为止，数据报大小为 4 并使用 4 个哈希来计算 SimHash。我尝试了各种其他组合，但到目前为止，这个组合产生了最好的结果。

我遇到的问题是这种方法在我拥有的数据集中找到了大约 80% 的重复项。我知道这一点是因为我已经根据上面提到的极其缓慢的 O(n^2) 完全匹配验证了整个数据集。O(n^2) 匹配器适用于小于 10^4 的数据集，但很快变得不可行，因为我需要运行大小为 10^8 的集。

关于如何提高 SimHash 的准确性以便更多“相似”记录被标记为相同的 SimHash 编号的任何想法、建议或想法？

编辑：在 SimHashing 之前，我将所有 ![0-9A-Z] 字符大写并删除。应该匹配的例子（拼写错误是故意的）：