algorithm - 是否有“Detecting NearDuplicates for Web Crawling”中描述的想法的实现

Question

论文：http ://www2007.org/papers/paper215.pdf

我只是想知道该论文第3章是否有任何实现。我的意思是在大型数据集之间进行查询，而不仅仅是 simhash（很容易找到 simhash 实现）。

谢谢~

Answer 1

Here is one though I haven't tested it works. The good thing its opensource.

Answer 2

这是Data mining和中的一个问题similarity search。有许多文章描述了如何做到这一点，并扩展到海量数据。

我有一个维基百科的实现（github：mksteve，集群，在我的博客中有一些关于它的评论）：度量树 。这要求您所做的测量满足三角不等式（维基百科：度量空间。即从项目 A 到项目 C 的度量距离小于或等于距离 A 到 B + 距离 B 到 C。

鉴于这种不平等，可以修剪搜索空间，因此只搜索可能与您的目标区域重叠的子树。如果该功能不成立（度量空间）。

simhash 中差异的位数可能是度量空间。

这些数据集的一般用法，在文档中提到 mapReduce 时提到，它通常在hadoop cluster. 每个处理节点都被赋予一个数据子集，并从它们的本地数据集中找到一组目标匹配。然后将这些组合在一起以给出类似项目的完全排序列表。

有一些论文（不确定参考文献）提到在集群中使用 m-tree，其中搜索空间的不同部分被分配给不同的集群，但我不确定 hadoop 基础结构是否支持使用如此高的层次抽象。