Unir similitud usando Hadoop

Question

Soy nuevo en hadoop. Quisiera dirigir algunos enfoques contigo que se me ocurrieron.

Problema:
2 conjuntos de datos: A y B.
Ambos conjuntos de datos representan canciones: algunos atributos de nivel superior, títulos (1 ..), artistas (1) ...
Necesito hacer corresponder estos conjuntos de datos utilizando algoritmos de igualdad o difusos (como levenshtein, jaccard, jaro-winkler, etc.) en función de los títulos y el intérprete.
Los tamaños de los conjuntos de datos son: A = 20-30M, B ~ = 1-6M.

Así que aquí hay enfoques que se me ocurrió:

1. Cargar conjunto de datos B (el más pequeño) en HDFS. Use mapreduce contra el conjunto de datos A (el más grande), donde:
   fase del mapa: para cada registro en A, acceda a HDFS y extraiga los registros B para buscar coincidencias;
   reducir fase: escribe pares id

2. conjunto de datos de carga A en la caché distirubted (es decir jboss caché) en forma optimizada para acelerar la búsqueda. Utilice mapreduce contra el conjunto de datos B, donde:
   fase mapa: para cada registro en la consulta B distribuye caché para hacer coincidir
   reducir: escribe pares id

3. uso mapreduce para unirse a ambos conjuntos de datos, donde
   fase mapa: crear una grabar desde el conjunto A y establecer B, hace coincidir
   fase de reducción: el mismo
   (estoy confundido con este. 1st: join será el producto cartesiano con un billón de registros; segundo: no estoy seguro de cómo hadoop puede paralisar eso a través clúster)

4. utilizar la colmena (estoy mirando ahora tratando de encontrar la manera de plugin de funciones personalizadas que harán la coincidencia de cadenas)

estoy loooking por unos punteros, qué enfoque sería el mejor candidato o tal vez hay hay otros enfoques que no veo.

Answer 1

Usted puede encontrar este documento y código útil:

Efficient Parallel Set-Similarity Joins Using MapReduce

he aplicado personalmente en Cascading con buenos resultados. Lamentablemente, el código es demasiado específico del dominio para su lanzamiento.

El objetivo del trabajo anterior es reducir el número de combinaciones para los pares candidatos que son muy similares, luego los pares candidatos se pueden comparar directamente (en una unión MR) utilizando cualquier combinación de algoritmos que sean relevantes. Un buen efecto secundario es que esta unión se puede realizar de manera uniforme en todo el clúster sin comparaciones duplicadas.

En definitiva, se trata de una optimización para realizar una combinación cruzada entre dos conjuntos independientes o dentro del mismo conjunto (el segundo caso se implementó de forma ligeramente diferente que el primero).

divulgación: yo soy el autor de conexión en cascada

Answer 2

Es posible que desee mirar a estos dos documentos de Jimmy Lin:

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

El planteamiento que adopte dependerá de qué tipo de métrica de similitud que utilice, pero un enfoque basado en Lucene puede funcionar aquí. También es posible que desee pensar en formas de dividir los datos para reducir la cantidad de comparaciones que necesita realizar.

Answer 3

echar un vistazo a

1. http://dbs.uni-leipzig.de/en/publication/learning_based_er_with_mr -> Evaluación de la prodzuct cartesiano de dos entradas (grande) establece

   Sin embargo, usted debería intentar evitar el cálculo de similitud por pares (Levenshtein, etc.) en el producto cartesiano. Incluso con grupos grandes, llevará horas o días, incluso para conjuntos de datos medianos.

2. http://dbs.uni-leipzig.de/en/publication/lb_for_mr_based_er -> Explica cómo bloqueo/La agrupación se acerca a la comparación por pares por racimo se puede realizar garantizando al mismo tiempo tareas uniformemente cargados (individual y de doble fuente)