CentralMatch: A fast and accurate method to identify blog-duplicates

A group of documents is called near-duplicates if they are almost the same with just a slight difference. Since near-duplicates are major concerns of Web search engines, it is necessary to identify and filter them effectively. Among existing near-duplicate identification methods, MinHashing is the most well-known one. It identifies near-duplicates regardless of locations of different parts in two documents. In blog environment, however, most near-duplicates differ only in their beginning or end. According to our preliminary experiment, about 99% of near-duplicates differ in the beginning or end (blog-duplicates hereafter) and only 1% of them differ in the middle. Thus, blog-duplicates have a long matched sequence in their central parts. Based on this important observation, we present a novel algorithm, CentralMatch, to identify blog-duplicates efficiently and accurately. When searching a document database for possible blog-duplicates of a given document, CentralMatch runs 50 times faster than MinHashing. In addition, CentralMatch identifies blog-duplicates more accurately than MinHashing. According to our experiments, when the precisions of Min-Hashing and CentralMatch are fixed to 0.9, their recalls are around 0.5 and 0.9, respectively, which means CentralMatch finds 80% more blog-duplicates than MinHashing.