Сходство с использованием Hadoop

Question

Я новичок в hadoop. Я хотел бы с вами подвести некоторые подходы, которые я придумал.

Проблема:
2 наборов данные: А и Б.
Оба набора данных представляют собой песню: некоторые атрибуты верхнего уровня, заголовки (1 .. ), исполнитель (1 ..).
Мне нужно сопоставить эти наборы данных либо с использованием равенства или нечетких алгоритмов (таких как levenshtein, jaccard, jaro-winkler и т. Д.) На основе названий и исполнителей.
Размеры набора данных: A = 20-30M, B ~ = 1-6M.

Так вот есть подходы, которые я придумал:

1. нагрузки набора данных B (наименьший) в HDFS. Используйте mapreduce против набора данных A (самый большой), где:
   фаза карты: для каждой записи в доступе HDFS и записи тяги B для сопоставления;
   уменьшение фазы: записывает пары ID

2. нагрузку набор данных A в distirubted кэша (т.е. JBoss кэш) в оптимизированной форме, чтобы ускорить поиск. Используйте MapReduce против набора данных B, где:
   карты фазы: для каждой записи в B запросе распределенного кэш для сопоставления
   уменьшить: пишет пары ID

3. использовать MapReduce, чтобы присоединиться как наборы данных, где
   карты фазы: Получает запись из набора A и набора B, соответствует
   фаза уменьшения: то же самое
   (я нечеткий о том, 1-й: соединение будет декартовым продуктом с триллионом записей; 2-й: не уверен, как хаоп может парализовать это через кластер)

4. использовать улей (я смотрю на прямо сейчас, пытаясь выяснить, как плагин пользовательских функций, которые будут делать сопоставление строк)

Я loooking за указатели, какой подход был бы лучшим кандидатом или могут быть, есть некоторые другие подходы, которые я не вижу.

Answer 1

Вы можете найти этот документ и код полезным:

Efficient Parallel Set-Similarity Joins Using MapReduce

Я лично реализовал его в Cascading с хорошими результатами. К сожалению, код слишком специфичен для выпуска.

Пункт указанной работы состоит в том, чтобы уменьшить число совпадений с парами-кандидатами, которые очень похожи друг на друга, тогда пары-кандидаты могут сравниваться непосредственно (в соединении с MR) с использованием любого подходящего алгоритма алгоритмов. Хорошим побочным эффектом является то, что это объединение может выполняться равномерно по всему кластеру без повторных сравнений.

В конечном счете это оптимизация при выполнении перекрестного соединения между двумя независимыми наборами или внутри одного и того же набора (второй случай реализован немного иначе, чем первый).

раскрытие: Я автор каскадного

Answer 2

Вы можете посмотреть на этих двух работах Джимми Лин:

• Brute Force and Indexed Approaches to Pairwise Document Similarity
• Pairwise Document Similarity in Large Collections with MapReduce

Подход, вы принимаете будет зависеть от того, какие сходства метрики вы используете, но здесь может работать подход, основанный на Lucene. Вы также можете подумать о способах разделения данных, чтобы уменьшить количество сравнений, которые вам нужно выполнить.

Answer 3

Взгляните на

1. http://dbs.uni-leipzig.de/en/publication/learning_based_er_with_mr -> Оценка декартова prodzuct двух (большой) входных наборов

   Однако вам должен действительно стараться избегать параллельных вычислений подобия (Левенштейн и т. д.) на декартовом произведении. Даже с большими кластерами это потребует от нескольких часов до нескольких дней даже для наборов данных среднего размера.

2. http://dbs.uni-leipzig.de/en/publication/lb_for_mr_based_er -> Объясняет, как блокировки/кластеризация подходов с парным сравнением в кластер может быть реализовано, обеспечивая при этом равномерно нагруженные задачи (с одним и двумя исходными кодами)