问题标签 [minhash]

我读过关于 kd-trees 的文章，但是当空间的维度很高时它们效率低下。我有一个值数据库，我想找到查询的某个汉明距离内的值。例如，数据库是一个 32 位数字的列表，我想找到与查询值相差小于 3 位的所有数字。

我在某处听说过 MultiVariate Partition 树，但找不到好的参考。我知道 min-Hash 给出了一个很好的近似值，更好，但我想要一个准确的答案。

我正在使用 MinHash 算法来查找图像之间的相似图像。我遇到过这篇文章，How can I recognize slightly modified images?它指向了MinHash算法。

我正在使用这篇博文中的 C# 实现，Set Similarity and Min Hash.

但是在尝试使用该实现时，我遇到了两个问题。

• 我应该将值设置为什么值universe？
• 将图像字节数组传递给HashSet时，它只包含不同的字节值；因此比较 1 ~ 256 的值。

universeMinHash 中这是什么？
我可以做些什么来改进 C# MinHash 实现？

由于HashSet<byte>包含高达 256 的值，因此相似度值始终为 1。

以下是使用 C# MinHash 实现的源代码Set Similarity and Min Hash：

有没有办法设置使用 ruby​​ 散列函数的种子值（即 1.9 中的杂音散列，不知道 JRuby？），这样我每次运行脚本时都可以获得相同的散列码（即在多个进程或在不同的节点上）

以便

提出“这是一个测试”.hash

每当我运行它时，今天，明天，从现在起的 3 周等时都是一样的

我想这样做，这样我就可以并行实现 MinHash

我可以在 murmur_hash gem 中看到 murmur 哈希接受种子，所以我假设我可以设置种子并在选择相同种子时确定性地获取哈希码

我有大型 postgresql 数据库，包含文档。每个文档都表示为表中的一行。当新文档添加到数据库中时，我需要检查重复项。但我不能只select用来找到完全匹配。两个文档可能略有不同，但仍然可以被视为重复，例如，如果一些次要字段不同而所有其他字段都相同。

我研究这个问题并找到解决这个问题的方法。可以MinHash为每个文档计算签名并构建倒排索引，从数据库中查询相似的文档。但我不明白如何映射MinHash到关系数据库。

据我了解，MinHash签名是 N 个哈希的列表，其中 N 是许多属性。相似度计算如下：

如果您已经有两个签名，这很简单，问题是在数据库中找到相似度小于或等于某个值的所有文档（具有相应签名）。

例如，我可以创建具有多个列的表，如下所示：

每minhashX列对应于文档属性之一的 minhash，并且docid是文档的标识符。我可以这样查询类似的记录：

其中minhash2searchX是新文档的 minhashes，而 THRESHOLD 是最小相似性。但是这种方法需要全扫描。有什么方法可以加速这个算法吗？

我已经阅读了很多教程、文档和使用 min-hash 实现 LSH（位置敏感散列）的代码片段。

LSH 试图通过散列随机子集并聚合它们来找到两个集合的 Jaccard 系数。我查看了 code.google.com 中的实现，但也无法理解他们的方法。我了解论文Google 新闻个性化：可扩展的在线协作过滤，但我无法理解其中的任何实现。

有人可以用简单的话解释一下如何用 MinHash 实现 LSH 吗？

我正在尝试寻找可以用于我的工作的 minhash 开源实现。

我需要的功能非常简单，给定一个集合作为输入，实现应该返回它的 minhash。

最好使用 python 或 C 实现，以防万一我需要破解它来为我工作。

任何指针都会有很大帮助。

问候。

我正在阅读 MinHash 技术来估计 2 个集合之间的相似性：给定集合 A 和 B，h 是散列函数，hmin(S) 是集合 S 的最小散列，即 hmin(S)=min(h(s )) 对于 S 中的 s。我们有以下等式：

p(hmin(A)=hmin(B))=|A∩B| / |A∪B|

这意味着A的最小哈希等于B的最小哈希的概率是A和B的Jaccard相似度。

我试图证明上述等式并提出我自己的证明：对于 a∈A 和 b∈B 使得 h(a)=hmin(A) 和 h(b)=hmin(B)。因此，如果 hmin(A)=hmin(B)，则 h(a)=h(b)。假设散列函数 h 可以将键散列到不同的散列值，所以 h(a)=h(b) 当且仅当 a=b，其概率为 |A∩B| / |A∪B|。但是，我的证明并不完整，因为哈希函数可以为不同的键返回相同的值。所以，我请求你帮助找到一个可以应用的证明，不管散列函数。

我在用 ：

hadoop-1.2.1 和 mahout-distribution-0.8

当我尝试使用以下命令运行 HASHMIN 方法时：

我收到此错误：

我很感激任何想法

我在实施 minhashing 时遇到问题。在纸上和阅读中，我理解了这个概念，但我的问题是排列“技巧”。而不是置换集合和值的矩阵，实现的建议是：“选择 k（例如 100）个独立哈希函数”，然后算法说：

在不同的小例子和教学书中，他们只使用了 (h = a*x + b mod p) 形式的两个或三个哈希函数。这很容易找到，但在实践中怎么做，我怎样才能找到100个这样的独立函数。

在此处的 Java 示例中，仅从一个哈希函数而不是多个哈希函数生成哈希值，与行索引无关。区别在哪里？我现在的问题是如何找到这些独立的散列函数，或者如果有一种只有一个散列函数的方法如何在算法中处理这些值？

我试图在 python 中理解/实现基于 minHash 的 jaccard 相似性。主要目标是在 MapReduce 中使用它。但是我不清楚哈希函数和签名长度的选择如何影响计算jaccard相似度的错误率。从维基百科中，我发现与计算的 jaccard 相似度相关的签名 (K) 和错误 (e) 的一般长度是 k = O(1/e^2)。我尝试在 python 中实现 minHash：

在我的测试中，我发现准确度随着签名长度的增加而增加，但随后它开始下降（或保持稳定）。我想知道是不是因为选择了哈希函数。如果是，有人可以建议使用一个好的散列函数。

我找到了一些相关的帖子，但仍然不清楚： minhash 算法中需要多少个哈希函数