TAILIEUCHUNG - Báo cáo khoa học: "Pairwise Document Similarity in Large Collections with MapReduce"

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 @ 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 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

• Báo cáo khoa học
• Pairwise Document Similarity
• Large Collections with MapReduce
• Tamer Elsayed
• báo cáo khoa học
• báo cáo ngôn ngữ
• xử lý ngôn ngữ tự nhiên
• Bài giảng Xử lý ngôn ngữ tự nhiên
• Ngôn ngữ tự nhiên
• Kỹ thuật lập trình
• Xử lý nhập nhằng ngữ nghĩa
• Xử lý ngữ nghĩa
• Xử lý ngôn ngữ
• Natural Language Processing
• Ngôn ngữ lập trình
• Nhập nhằng cấu trúc
• Tri thức về ngôn ngữ
• Mô hình ngôn ngữ
• Mô hình n gram
• Dịch máy
• Phương pháp dịch máy
• Hiểu ngôn ngữ
• Phân tích ngữ nghĩa
• Phân loại tin tự động
• Biểu diễn vị từ
• Thuộc tính về sự kiện
• Thuộc tính về sự kiện
• Mô hình ngôn ngữ Google Book N grams
• Mô hình ngôn ngữ KenLM
• Phương pháp làm mịn
• Tách từ tiếng Việt
• Gán nhãn từ loại
• Phân tích cú pháp
• Nghĩa từ vựng
• Phân giải nhập nhằng từ
• Phân loại văn bản
• Lexical chain
• Phản hồi thông tin
• Bài toán PTCP
• Cấu trúc ngữ pháp
• Phân tích cú pháp xác suất
• CKY kết hợp xác suất
• Văn phạm phi ngữ cảnh xác suất
• Hình thái học