Вывод дедупликации SimHash в MapReduce

Я реализую алгоритм 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

Значение - это текст документа

Вывод:

Ключ - это полоса # + битовая строка

Значение - это текст документа.

Но теперь я запутался в редукторе. Я не хочу, чтобы в окончательном наборе данных были конфликты, но какова на это гарантия? Я не понимаю, каким должно быть выходное значение ключа?

Обновление (дополнительные пояснения) Если входной ключ редуктора - это диапазон # + ​​битовая строка, а значение - это документы с тем же диапазоном. Например

Band0+{101} = Doc1,Doc3

Расстояние Хэмминга можно рассчитать, чтобы узнать дубликаты документов. Но каждая группа (набор) может иметь конфликты в одном или нескольких документах, поскольку нет гарантии, что одни и те же документы попадут в один и тот же редуктор.

Например, если первая группа - это Doc1, Doc2, Doc3, а вторая группа - это Doc2, Doc3, Doc4. И Doc2 и Doc3 являются дубликатами. Как я могу вывести уникальные документы как Doc1, Doc3 и Doc4?

Я столкнулся с этими вопросами, но они мне не очень помогли:

  1. Определение пары ключ-значение для дедупликации с использованием hadoop mapreduce < / а>
  2. Как реализовать LSH с помощью MapReduce?

[1] М. Чарикар, «Методы оценки подобия из алгоритма округления», Proc. 34-го ежегодного симпозиума по теории вычислений (STOC), 2008 г., стр. 380-388.


java hadoop mapreduce deduplication
person Daisy    schedule 04.09.2015    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Для каждого документа вы можете выдать 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 и т. Д.

person RojoSam    schedule 07.09.2015
comment
Спасибо за Ваш ответ. Что ж, вы правы, и тогда я могу измерить расстояние Хэмминга между каждой группой, чтобы узнать дубликаты документов. Но у каждой группы могут быть конфликты в одном или нескольких документах, поскольку нет гарантии, что одни и те же документы попадут в один и тот же редуктор. Например, если первая группа - это Doc1, Doc2, Doc3, а вторая группа - это Doc2, Doc3, Doc4. И Doc2 и Doc3 являются дубликатами. Как я могу вывести уникальные документы как Doc1, Doc3 и Doc4? - person Daisy; 07.09.2015
comment
Один из вариантов - иметь более одного задания MapReduce. В первом задании вы можете идентифицировать дублированные документы, а во втором вы можете отфильтровать дублированные, чтобы удалить их из вывода. Задача состоит в том, чтобы всегда сохранить один и тот же документ и отказаться от другого. - person RojoSam; 07.09.2015
comment
В вашем примере: OutputGroup1 - ›(Doc1ID, Doc1), (Doc2ID, ‹REMOVE_MARK›), (Doc3ID, Doc3) __ OutputGroup2 -› (Doc2ID, ‹REMOVE_MARK), (Doc3ID, Doc3), (Doc4ID, Doc4); где кортежи (ключ, значение). Затем во втором редукторе (во втором MapReduce) вы группируете по идентификатору документа, и если хотя бы какая-то запись помечена как для удаления, тогда вы не пишете в выводе этот документ (возможно, что в одной группе документ 2 был помечен как дублированный, а в другой - нет). - person RojoSam; 07.09.2015