¿Cómo implementar self-join/cross-product con hadoop?

mapreduce

Question

Es una tarea común hacer una evaluación de los pares de elementos: ejemplos: deduplicación, filtrado colaborativo, elementos similares, etc. Esto es básicamente auto unión o producto cruzado con la misma fuente de datos.

Answer 1

Uno típicamente usa el reductor para realizar cualquier lógica que se requiera en la unión. El truco es mapear el conjunto de datos dos veces, posiblemente agregando un marcador al valor que indica qué ejecución es. Entonces una auto unión no es diferente de cualquier otro tipo de unión.

Answer 2

Para hacer una auto unión, puede seguir el patrón "reducir unión lateral". El asignador emite la combinación / clave externa como clave, y el registro como el valor.

Entonces, digamos que queríamos hacer una auto-unión en "city" (la columna del medio) en los siguientes datos:

don,baltimore,12
jerry,boston,19
bob,baltimore,99
cameron,baltimore,13
james,seattle,1
peter,seattle,2

El mapeador emitiría los pares clave-> valor:

(baltimore -> don,12)
(boston -> jerry,19)
(baltimore -> bob,99)
(baltimore -> cameron,13)
(seattle -> james,1)
(seattle -> peter,2)

En el reductor, obtendremos esto:

(baltimore -> [(don,12), (bob,99), (cameron,13)])
(boston -> [(jerry,19)])
(seattle -> [(james,1), (peter,2)])

Desde aquí, puede hacer la lógica de unión interna, si así lo desea. Para hacer esto, emparejaría cada elemento para cada otro artículo. Para hacerlo, cargue los datos en una lista de arreglos, luego realice un ciclo N x N sobre los elementos para compararlos entre sí.

Tenga en cuenta que las uniones reducidas son costosas. Envían prácticamente todos los datos a los reductores si no filtra nada. Además, tenga cuidado de cargar los datos en la memoria en los reductores. Puede explotar su pila en una clave de combinación activa cargando todos los datos en una lista de matriz.

Lo anterior es un poco diferente de la típica unión del lado reductor. La idea es la misma al unir dos conjuntos de datos: la clave externa es la clave y el registro es el valor. La única diferencia es que los valores podrían provenir de dos o más conjuntos de datos. Puede usar MultipleInputs para que diferentes mapeadores analicen diferentes conjuntos de entrada, luego haga que el reductor recopile datos de ambos.

El producto cruzado en el caso de que no tenga ninguna restricción es una pesadilla. Es decir,

select * from tablea, tableb;

hay muchas maneras de hacer esto. Ninguno de ellos es particularmente eficiente. Si quieres este tipo de comportamiento, déjame un comentario y pasaré más tiempo explicando una forma de hacerlo.

Si puede encontrar algún tipo de combinación clave que es una clave fundamental para la similitud, está mucho mejor.

Enchufe para mi libro: Patrones de diseño de MapReduce . Debería publicarse dentro de unos meses, pero si está realmente interesado, puedo enviarle el capítulo sobre uniones.