问题标签 [locality-sensitive-hash]

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

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

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

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

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

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

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

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

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

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

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

哈希表

哈希表

主文件

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

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

我有两个名称和一个地址的“记录”（基本上是 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] 字符大写并删除。应该匹配的例子（拼写错误是故意的）：

• JOHN SMITH, 123 ANY STREET Sometown ZIP
• 约翰尼·史密斯，123 岁
• SOMETOWNE ZIP ROBERT PARKER, 442 ANY STREET SOMETOWN ZIP

这里1和2是相似的，3不是。输出应该是：1 + 2

我正在寻找一个轻量级的 Java 库，该库支持按位置敏感散列的最近邻搜索，用于在具有数十万个数据点的高维（在我的情况下为 32）数据集中几乎均匀分布的数据。

获取存储桶中的所有条目以进行查询是完全足够好的。考虑到我的问题包括的一些过滤器参数，然后可以以不同的方式处理我真正需要的那些。

我已经找到了likelike，但希望有一些更小的东西，不需要任何其他工具（比如likelike的Apache Hadoop）。

我注意到 LSH 似乎是找到具有高维度属性的类似项目的好方法。

阅读论文http://www.slaney.org/malcolm/yahoo/Slaney2008-LSHTutorial.pdf后，我仍然对这些公式感到困惑。

有谁知道解释这个简单方法的博客或文章？

我想要一个最近邻搜索（NNS）问题的算法。该问题与计算几何领域有关。我搜索了很多，但我没有找到一个算法。我认为局部敏感哈希（LSH）算法会很好地解决这个问题，但不幸的是我没有找到解决这个问题的算法。正是我想要一篇文章来学习 LSH。谁能帮我？

谢谢

我正在研究音频指纹识别系统，最近阅读了一些论文和研究，尤其是这个页面：c# AudioFingerprinting and Locality Sensitive Hashing

我现在每 32 毫秒的音频就有一系列指纹。我想要做的是使用 LSH 或其他一些相似性保留方法对这些单独的指纹（而不是它们的序列）进行哈希处理。根据我对 LSH 的了解，它适用于多维向量并生成二进制字符串，然后可以在汉明空间中进行比较。

我的问题是我拥有的指纹不是多维的。它们只是单个长整数。我如何使用 LSH 对这些进行哈希处理？是否有任何方法来散列（以保持相似性的方式）一维标量？

我无法回答我的问题。

我需要一种哈希方法，它会生成一个哈希值，可以与其他哈希值进行比较并找出保真度，

假设我必须有 2 个字符串，“mother”，“father”，当我比较 2 个哈希值时，它会说由于“ther”，它们之间存在保真度。

是否有任何哈希方法可以做到这一点？

谢谢你