我对检测相似文档的技术有一个合理的理解，该技术首先计算它们的 minhash 签名（从它们的 shingles 或 n-gram），然后使用基于 LSH 的算法来有效地对它们进行聚类（即避免二次复杂度，这将需要一个简单的成对穷举搜索）。

我正在尝试做的是桥接三种不同的算法，我认为这些算法都与这个 minhash + LSH 框架有关，但以非显而易见的方式：

（1） Mining of Massive Datasets（Rajaraman and Ullman）一书第3章第3.4.3节勾勒的算法，似乎是minhashing的规范描述

(2) Ryan Moulton 的Simple Simhashing文章

（3）Charikar所谓的SimHash算法，本文介绍

我觉得这很令人困惑，因为我假设虽然 (2) 使用术语“simhashing”，但它实际上是以类似于 (1) 的方式进行 minhashing，但关键区别在于集群只能由单个签名表示（甚至可能涉及复杂的多个哈希函数），而两个文档有更多与（1）相似的机会，因为签名可以在多个“带”中发生冲突。(3) 似乎完全不同，因为签名是根据它们的汉明距离进行比较的，而 LSH 技术意味着对签名进行多次排序，而不是对它们进行捆绑。我还看到（在其他地方）最后一种技术可以包含加权的概念，它可以用来更加强调某些文档部分，而这似乎在 (1) 和 (2) 中缺乏。

所以最后，我的两个问题：

(a) 是否有一种（令人满意的）方法可以连接这三种算法？

(b) 有没有办法将权重概念从 (3) 导入到 (1)？

我正在实现一个近邻搜索应用程序，它将找到类似的文档。到目前为止，我已经阅读了很多 LSH 相关材料（LSH 背后的理论有点令人困惑，我还不能 100% 理解它）。

我的代码能够使用 minhash 函数计算签名矩阵（我接近尾声）。我还在签名矩阵上应用了条带策略。但是我无法理解如何将带中的签名向量（列）散列到桶中。

我的最后一个问题可能是最重要的一个，但我必须问一些introduction问题：

q1：散列函数是否只会将相同的向量映射到同一个桶？（假设我们有足够的桶）

q2：哈希函数是否应该将相似的向量映射到同一个桶？如果是，那么这种相似性的程度/定义是什么，因为我不是在计算比较，而是在做散列。

q3：根据上面的问题，我应该使用什么样的哈希表算法？

q4：我认为我最弱的一点是我不知道如何生成一个以向量作为输入并选择一个桶作为输出的哈希函数。我可以根据 q1 和 q2 自己实现一个......关于为 LSH 生成散列函数有什么建议bucketing吗？

我正在用 Java 编写一个 minhashing 算法，它要求我生成任意数量的随机散列函数（在我的例子中为 240 个散列函数），并通过它运行任意数量的整数（目前为 2000 个）。

为了做到这一点，我一直在为 240 个散列函数中的每一个生成随机数 a、b 和 c（范围从 1 到 2001）。然后，我的哈希函数返回 h = ((a*x) + b) % c，其中 h 是返回值，x 是通过它的整数之一。

这是随机散列的有效实现，还是有更常见/可接受的方法来做到这一点？

这篇文章问了一个类似的问题，但我仍然对答案的措辞感到有些困惑： Minhash implementation how to find hash functions for permutations

参考论文Bundle Min Hashing for Logo Recognition：

假设我们有包 {2,5,18,444,678} 和 {2,5,79,368,841}，词汇量为 1M。如果我们每个包只有 1 个草图，那么我们是否只需要 1 个散列函数，它将 1M 整数确定性地散列为 [0,1] 中均匀分布的值。每次调用的散列函数必须有固定的种子。对于 4 幅草图，我们只需要具有 4 个种子的相同散列函数。想法是否正确？

或者我们可以从集合（捆绑）中随机选择一个数字作为最小哈希词，因为它们代表集合的随机排列？

论文中需要实现散列函数的任何参考？

MurmurHash3 可以完成这项工作吗？

嗨，伙计们。我对堆栈交换非常陌生，目前正在研究图论。

我要问的这组问题是非常介绍性的，因为我是初级程序员（不熟悉散列、桶、向量等数据结构方面的知识）。

我的想法是采用形式为（时间戳 t，节点 i，节点 j）的数据集，它表示在时间 t 时 i 和 j 之间存在一条边。这个想法是搜索每个节点的邻域集并将它们散列。如果他们的“向量”（我不明白那是什么）散列到同一个桶中 - 他们是集群形成的候选者。

但他的问题是我想做实验并尝试运行它。但是不知道如何实现哈希函数，然后将它们存储在一起。

我不是说帮我写代码。但是指针（伪代码）会很有帮助。就像告诉我初始化哈希表等

我熟悉 SimHash 和 MinHash 的 LSH（Locality Sensitive Hashing）技术。SimHash 在实值数据上使用余弦相似度。MinHash 计算二进制向量的相似度。但我无法决定使用哪个更好。

我正在为网站创建一个后端系统，以查找几乎重复的半结构化文本数据。例如，每条记录都有标题、位置和简短的文本描述（<500 字）。

除了特定的语言实现之外，哪种算法最适合新建生产系统？

问题很简单：我需要找到最佳策略来基于 Redis 的表示来实现准确的 HyperLogLog 联合——这包括在导出数据结构以供其他地方使用时处理它们的稀疏/密集表示。

两种策略

有两种策略，其中一种似乎非常简单。我查看了实际的 Redis 源代码，但我遇到了一些麻烦（我自己在 C 语言中并不大），从精度和效率的角度来看，使用他们的内置结构/例程或开发我自己的结构/例程是否更好. 对于它的价值，我愿意牺牲空间和一定程度的错误（stdev +-2%）来追求极大的集合效率。

一、包容原则

到目前为止，两者中最简单的——基本上我只会使用无损联合（PFMERGE）结合这个原则来计算重叠的估计值。测试似乎表明在许多情况下这种运行可靠，尽管我无法准确处理实际效率和准确性（某些情况下会产生 20-40% 的错误，这在这个用例中是不可接受的）。

基本上：

或者，在多组的情况下......

似乎在许多情况下都能以良好的准确性工作，但我不知道我是否相信它。虽然 Redis 有许多内置的低基数修饰符旨在规避已知的 HLL 问题，但我不知道在大小差异很大的集合中是否仍然存在疯狂不准确的问题（使用包含/排除）......

2. Jaccard索引交集/MinHash

这种方式似乎更有趣，但我的一部分感觉它可能在计算上与 Redis 的一些现有优化重叠（即，我没有从头开始实现我自己的 HLL 算法）。

使用这种方法，我将使用 MinHash 算法对 bin 进行随机采样（我认为 LSH 实现不值得麻烦）。这将是一个单独的结构，但通过使用 minhash 获取集合的 Jaccard 索引，您可以有效地将联合基数乘以该索引以获得更准确的计数。

问题是，我不太精通 HLL，虽然我很想深入研究 Google 论文，但我需要一个可行的实施方案。有可能我忽略了 Redis 现有优化的一些基本考虑因素，或者在算法本身允许计算成本低的交集估计和相当宽松的置信范围。

因此，我的问题：

如果我愿意牺牲空间（并在较小程度上牺牲准确性），如何使用 redis 最有效地获得 N 个巨大（十亿）集的计算成本低廉的交集估计？

假设我有五套我想聚类。我了解这里描述的 SimHashing 技术：

https://moultano.wordpress.com/2010/01/21/simple-simhashing-3kbzhsxyg4467-6/

例如，如果它的结果​​是：可以产生三个簇（{A}和{B,C,D}） ：{E}

同样，MMDS 书第 3 章中描述的 MinHashing 技术：

http://infolab.stanford.edu/~ullman/mmds/ch3.pdf

如果其结果是：也可以产生相同的三个集群：

（每组对应一个由三个“波段”组成的MH签名，如果至少有一个签​​名波段匹配，则将两组分组。更多的波段意味着更多的匹配机会。）

但是我有几个与这些相关的问题：

(1) SH可以理解为MH的单频段版本吗？

(2) MH 是否一定意味着使用像 Union-Find 这样的数据结构来构建集群？

(3) 我认为这两种技术中的集群实际上是“预集群”，从某种意义上说，它们只是“候选对”的集合，我是否正确？

(4) 如果 (3) 为真，是否意味着我仍然需要O(n^2)在每个“预集群”内进行搜索，以将它们进一步划分为“真实”集群？（如果我有很多小且相当平衡的预集群，这可能是合理的，否则就不是了）

我目前正在使用MinHashing技术进行文档聚类。但是，我没有得到想要的结果，因为 MinHash 是一个粗略的估计，Jaccard similarity它不符合我的要求。

这是我的场景：

我有一大堆书，如果给出一个单页作为查询，我需要找到从中获取该页的相应书。限制是，我有整本书的功能，不可能逐页获得这些书的功能。在这种情况下，如果书太大，Jaccard 相似性会给出很差的结果。我真正想要的是查询页面和书籍之间的距离（反之亦然）。那是：

给定2组A，B：我想要从A到B的距离，

是否有类似的距离度量可以给出从集合 A 到集合 B 的距离。此外，是否仍然可以使用MinHashing具有这种相似性度量的算法？

是否有任何插件允许在 Elasticsearch 上使用 LSH？如果是的话，你能指出我的位置并告诉我如何使用它吗？谢谢

编辑：我发现 ES 使用 MinHash 插件。我怎么能用这个来比较文件呢？什么是查找重复项的好设置？