Bloom filters para mejorar la peformance un join MR

[Pere Ferrera]

Interesante artículo y librería open-source para Cascading: http://blog.liveramp.com/2013/04/03/bloomjoin-bloomfilter-cogroup/

Para el caso de un join en MapReduce donde hay un dataset muy grande y otro pequeño, proponen construir un Bloom Filter usando el dataset pequeño. Luego este Bloom Filter se carga en memoria en los Mappers y permite filtrar el dataset grande. Por las propiedades del Bloom Filter, los elementos que se descarten seguro que no tendrán elemento correspondiente en el dataset pequeño, aunque puede haber falsos positivos, en cuyo caso se filtra normalmente en el Reducer. De este modo se puede implementar un inner join de manera mucho más eficiente ya que muchos datos son filtrados antes de la fase del shuffle, que es la más costosa en MapReduce.

Saludo,

[Marc de Palol]

esto es una GRAN idea.

On 04/04/2013 18:14, Pere Ferrera wrote:
> Interesante art�culo y librer�a open-source para Cascading:

> http://blog.liveramp.com/2013/04/03/bloomjoin-bloomfilter-cogroup/
>
> Para el caso de un join en MapReduce donde hay un dataset muy grande y

> otro peque�o, proponen construir un Bloom Filter usando el dataset
> peque�o. Luego este Bloom Filter se carga en memoria en los Mappers y

> permite filtrar el dataset grande. Por las propiedades del Bloom

> Filter, los elementos que se descarten seguro que no tendr�n elemento
> correspondiente en el dataset peque�o, aunque puede haber falsos

> positivos, en cuyo caso se filtra normalmente en el Reducer. De este

> modo se puede implementar un inner join de manera mucho m�s eficiente

> ya que muchos datos son filtrados antes de la fase del shuffle, que es

> la m�s costosa en MapReduce.
>
> Saludo,
> --
> Has recibido este mensaje porque est�s suscrito al grupo
> "spain-scalability-users" de Grupos de Google.
> Para anular la suscripci�n a este grupo y dejar de recibir sus correos
> electr�nicos, env�a un correo electr�nico a
> spain-scalability...@googlegroups.com.
> Para obtener m�s opciones, visita
> https://groups.google.com/groups/opt_out.
>
>

[Iván de Praadoo]

Es interesante, pero sólo para el caso de inner joins donde vaya a haber un filtrado muy potente... De otra manera no mejoraría mucho con respecto a un reduce join de toda la vida (o empeoraría). 

Iván

2013/4/4 Marc de Palol <phle...@gmail.com>

esto es una GRAN idea.

On 04/04/2013 18:14, Pere Ferrera wrote:

Interesante artículo y librería open-source para Cascading: http://blog.liveramp.com/2013/04/03/bloomjoin-bloomfilter-cogroup/

Para el caso de un join en MapReduce donde hay un dataset muy grande y otro pequeño, proponen construir un Bloom Filter usando el dataset pequeño. Luego este Bloom Filter se carga en memoria en los Mappers y permite filtrar el dataset grande. Por las propiedades del Bloom Filter, los elementos que se descarten seguro que no tendrán elemento correspondiente en el dataset pequeño, aunque puede haber falsos positivos, en cuyo caso se filtra normalmente en el Reducer. De este modo se puede implementar un inner join de manera mucho más eficiente ya que muchos datos son filtrados antes de la fase del shuffle, que es la más costosa en MapReduce.

Saludo,
--
Has recibido este mensaje porque estás suscrito al grupo "spain-scalability-users" de Grupos de Google.
Para anular la suscripción a este grupo y dejar de recibir sus correos electrónicos, envía un correo electrónico a spain-scalability-users+unsub...@googlegroups.com.
Para obtener más opciones, visita https://groups.google.com/groups/opt_out.

--
Has recibido este mensaje porque estás suscrito al grupo "spain-scalability-users" de Grupos de Google.
Para anular la suscripción a este grupo y dejar de recibir sus correos electrónicos, envía un correo electrónico a spain-scalability-users+unsub...@googlegroups.com.
Para obtener más opciones, visita https://groups.google.com/groups/opt_out.