是否实现了“检测用于网络爬行的NearDuplicates”中描述的思想？

Question

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

我只是想知道这篇论文的第三章有什么实现。我指的是在大型数据集之间查询，而不仅仅是simhash (很容易找到simhash实现)。

谢谢~

Answer 1

这是one，虽然我还没有测试它的工作情况。好消息是它是开源的。

Answer 2

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

我有一个wikipedia : Metric tree的实现(github : mksteve, clustering，在我的blog中有一些关于它的注释)。这要求您所做的度量满足三角形不等式(wikipedia : Metric space。也就是说，从项目A到项目C的度量距离小于或等于距离A到B+距离B到C。

考虑到这种不等性，可以裁剪搜索空间，以便只搜索可能与目标区域重叠的子树。而该特征不为真(公制空间)。

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

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

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