Pairwise document similarity in large collections with MapReduce

This paper presents a MapReduce algorithm for computing pairwise document similarity in large document collections that exhibits linear growth in running time and space in terms of the number of documents.

Abstract

This paper presents a MapReduce algorithm for computing pairwise document similarity in large document collections. MapReduce is an attractive framework because it allows us to decompose the inner products involved in computing document similarity into separate multiplication and summation stages in a way that is well matched to efficient disk access patterns across several machines. On a collection consisting of approximately 900,000 newswire articles, our algorithm exhibits linear growth in running time and space in terms of the number of documents.