Сходство соединения с помощью Hadoop

Question

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

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

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

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

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

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

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

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

Answer 1

Эта статья и код могут оказаться полезными:

Эффективные соединения с параллельным набором сходств с использованием MapReduce

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

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

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

раскрытие: я автор каскадных

Answer 2

Взгляните на

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

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

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

Answer 3

Возможно, вы захотите взглянуть на эти две статьи Джимми Линя:

• Грубая сила и индексированные подходы к парному сходству документов
• Сходство парных документов в больших коллекциях с MapReduce

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