SimHash冗余输出在MapReduce中的应用

Question

我正在实现SimHash算法1，以便使用MapReduce去复制数据集。

例如，如果我有3个文档-- Doc1、Doc2、Doc3、Doc4。假设Doc1与汉明距离小于3的Doc3相似，那么完成去重复后输出的“唯一”数据集应该是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#+the位字符串。

值是文档文本。

但现在我对减速器感到困惑。我不想在最终的数据集中出现冲突，但这方面的保证是什么。我对什么是关键的价值产出感到困惑？

如果还原器输入键是位字符串，并且值是带相同带的文档，则为更新(更多解释)。例如

Band0+{101} = Doc1,Doc3

汉明距离可以计算，以了解重复的文件。但是每个组(集合)可能在一个或多个文档中存在冲突，因为不能保证相同的文档最终会在同一个减法器中结束。

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

我遇到了这些问题，但它们对我没有多大帮助：

1. Deciding key value pair for deduplication using hadoop mapreduce
2. How to implement LSH by MapReduce?

1 M. Charikar，“舍入算法中的相似估计技术”，Proc.第34届计算理论年会，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等也是如此。