java - MapReduce中的SimHash重复数据删除输出

Question

我正在实现SimHash算法[1]，以使用MapReduce对数据集进行重复数据删除。

例如，如果我有3个文档Doc1，Doc2，Doc3，Doc4。假设Doc1与Doc3相似，汉明距离小于3。然后，在执行重复数据删除后，输出“唯一”数据集应为Doc1，Doc2和Doc4。

我的实现包括将每个文档哈希转换为64位字符串，然后将该位字符串划分为频段以进行进一步匹配。
为了简单起见，让我们说:

Doc1 = band0+{101},band1+{110}
Doc2 = band0+{100},band1+{110}
Doc3 = band0+{101},band1+{110}
Doc4 = band0+{100},band1+{101}

如果我按照相似的频段对文档进行分组，则相似性的候选者将是:

1st set: Doc1, Doc3
2nd set: Doc2, Doc4
3rd set: Doc1, Doc2, Doc3

所以现在我要做的就是计算单个集合中每个候选者之间的汉明距离。

我试图实现映射器，其中:

输入:

关键是LongWritable偏移量

值是文件文字

输出:

键是band＃+位串

值是文档文本。

但是现在我对 reducer 感到困惑。我不想在最终数据集中出现冲突，但是这样做有什么保证。我对键值输出应该是什么感到困惑？

更新(更多说明)
如果reducer输入Key是band＃+ bit字符串，而Value是具有相同band的文档。
例如

Band0+{101} = Doc1,Doc3

可以计算汉明距离以知道重复的文档。但是每个组(一组)在一个或多个文档中可能有冲突，因为不能保证相同的文档将最终出现在相同的reducer中。

例如，如果第一组是Doc1，Doc2，Doc3，第二组是Doc2，Doc3，Doc4。 Doc2和Doc3是重复的如何将唯一文档输出为Doc1，Doc3和Doc4？

我遇到了以下问题，但它们对我的帮助不大:

Deciding key value pair for deduplication using hadoop mapreduce

How to implement LSH by MapReduce?

[1] Charikar，“四舍五入算法的相似度估计技术”，Proc.Natl.Acad.Sci.USA，87:3877-2，1999。第34届年度计算机理论研讨会(STOC)，2008年，第380-388页。

Answer 1

对于每个文档，您可以发出0个或更多输出，然后可以执行以下操作:

Input1: Doc1
Outputs
  key1: band0101, value1: Doc1
  key2: band1110, value2: Doc1

(one output for each band)

Input2: Doc2
Outputs
  key1: band0100, value1: Doc2
  key2: band1110, value2: Doc2
.
.
.

使用化简器中的此方法，您将获得键字符串为band0101分组的所有文档的列表。与band0100，band1110等相同