Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
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. . | Pairwise Document Similarity in Large Collections with MapReduce Tamer Elsayed Jimmy Lin and Douglas W. Oard Human Language Technology Center of Excellence and UMIACS Laboratory for Computational Linguistics and Information Processing University of Maryland College Park MD 20742 telsayed jimmylin oard @umd.edu 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. 1 Introduction Computing pairwise similarity on large document collections is a task common to a variety of problems such as clustering and cross-document coreference resolution. For example in the PubMed search engine 1 which provides access to the life sciences literature a more like this browsing feature is implemented as a simple lookup of documentdocument similarity scores computed offline. This paper considers a large class of similarity functions that can be expressed as an inner product of term weight vectors. For document collections that fit into randomaccess memory the solution is straightforward. As collection size grows however it ultimately becomes necessary to resort to disk storage at which point aligning computation order with disk access patterns becomes a challenge. Further growth in the Department of Computer Science t The iSchool College of Information Studies 1http www.ncbi.nlm.nih.gov PubMed document collection will ultimately make it desirable to spread the computation over several processors at which point interprocess communication becomes a second potential bottleneck for which
