Document similarity self-join with MapReduce
Lucchese C., Baraglia R., De Francisci Morales G.
Similarity Self-Join Database Management. Data mining Data Mining All Pair Similarity Parallel Algorithms
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.
Source: IEEE International Conference on Data Mining, pp. 731–736, Sydney, December 14-17 2010
Metrics
Back to previous page
@inproceedings{oai:it.cnr:prodotti:92154,
title = {Document similarity self-join with MapReduce},
author = {Lucchese C. and Baraglia R. and De Francisci Morales G.},
doi = {10.1109/icdm.2010.70},
booktitle = {IEEE International Conference on Data Mining, pp. 731–736, Sydney, December 14-17 2010},
year = {2010}
}
0000-0002-2415-494X