CoDet: A new algorithm for containment and near duplicate detection in text corpora

Abstract

Bu tezde, birbirine benzer doküman tespitinin genelleştirilmiş versiyonu olan bir dokümanıniçerdiği bilgilerin başka bir doküman tarafından içerilip içerilmediğini ortaya koyan kapsamatespiti konusu incelenmiştir. Yazılı dokümanlarda dokümanların birbirini kapsaması üç farklışekilde karşımıza çıkmaktadır: ilk durum dokümanların tamamen aynı olması, ikinci durumdokumanların oldukça benzer olması, üçüncü ve ilk iki durumun daha geniş kapsamlı haliise bir dokumanın diğerini içermesi.Kapsama tespiti için CoDet ismini verdiğimiz özelliklepeşisıra gelmekte olan haberler için kullanışlı yeni bir algoritma önermekteyiz. Ayrıcahavuzlama tekniği vasıtasıyla sınırlı insan yardımı kullanarak algoritmaların etkinliğini veverimliliğini güvenilir bir şekilde ölçmemizi sağlayan bir test koleksiyonu oluşturduk.CoDet'in performansını oldukça benzer doküman tespitinde kullanılan ve alanındabaşarılı kabul edilen dört farklı algoritma (DSC, full fingerprinting, I-Match ve SimHash)ile karşılaştırdık. Deneysel çalışmalarımızdan edindiğimiz bulgulara göre CoDet genelliklealternatif algoritmalardan daha iyi sonuç vermekte ve yazılı dokümanlar üzerindekapsama tespiti konusunda kaydadeğer sonuçlar üretmektedir.

In this thesis, we investigate containment detection, which is a generalized versionof the well known near-duplicate detection problem concerning whether adocument is a subset of another document. In text-based applications, there arethree ways of observing document containment: exact-duplicates, near-duplicates,or containments, where first two are the special cases of containment. To detectcontainments, we introduce CoDet, which is a novel algorithm that focusesparticularly on containment problem. We also construct a test collection using anovel pooling technique, which enables us to make reliable judgments for the relativeeffectiveness of algorithms using limited human assessments. We compare itsperformance with four well-known near duplicate detection methods (DSC, fullfingerprinting, I-Match, and SimHash) that are adapted to containment detection.Our algorithm is especially suitable for streaming news. It is also expandable todifferent domains. Experimental results show that CoDet mostly outperforms theother algorithms and produces remarkable results in detection of containments intext corpora.