Given a collection of objects, the Similarity Self-Join problem requires to discover all those pairs of objects whose similarity is above a user defined threshold. In this paper we focus on document collections, which are characterized by a sparseness that allows effective pruning strategies. Our contribution is a new parallel algorithm within the MapReduce framework. This work borrows from the state of the art in serial algorithms for similarity join and MapReduce-based techniques for set-similarity join. The proposed algorithm shows that it is possible to leverage a distributed file system to support communication patterns that do not naturally fit the MapReduce framework. Scalability is achieved by introducing a partitioning strategy able to overcome memory bottlenecks. Experimental evidence on real world data shows that our algorithm outperforms the state of the art by a factor 4.5. Â© 2010 IEEE.
|Data di pubblicazione:||2010|
|Titolo:||Document similarity self-join with MapReduce|
|Rivista:||PROCEEDINGS IEEE INTERNATIONAL CONFERENCE ON DATA MINING|
|Titolo del libro:||Proceedings - IEEE International Conference on Data Mining, ICDM|
|Digital Object Identifier (DOI):||http://dx.doi.org/10.1109/ICDM.2010.70|
|Appare nelle tipologie:||4.1 Articolo in Atti di convegno|