Finding Top-k Similar Document Pairs - speeding up a multi-document summarization approach
Ladda ner
Typ
Examensarbete för masterexamen
Master Thesis
Master Thesis
Program
Computer science – algorithms, languages and logic (MPALG), MSc
Publicerad
2014
Författare
Toft, Johan
Bogren, Emma
Modellbyggare
Tidskriftstitel
ISSN
Volymtitel
Utgivare
Sammanfattning
Today there exist many approaches to multi-document summarization, which is the task of automatically creating a summary from multiple sources. This can be a complicated problem, but in this thesis we have focused on a simple approach that is currently being researched. The idea is to find the pairs of documents with the largest overlaps in words and use these to produce a summary. Originally, the algorithm used for this was very naive, comparing each word of every possible pair of documents, and the aim of this project has been to make it more efficient. We have reviewed existing algorithms used for similar problems, and found two useful ones: TOP-MATA and Topk Join. We have also created a new algorithm which we call the Segment Bounding Algorithm (SBA). The approaches were evaluated on two data sets - TREC and Opinosis - and the experimental results showed that SBA was the most efficient on the documents of TREC, while Top-k Join performed slightly better than SBA on the shorter documents of Opinosis. SBA was in the end proposed as an improvement of the simple summarization approach.
Beskrivning
Ämne/nyckelord
Data- och informationsvetenskap , Informations- och kommunikationsteknik , Computer and Information Science , Information & Communication Technology