Near-Duplicate Detection Based on Text Coherence Quantification
Joris D’hondt, Paul-Armand Verhaegen, Joris Vertommen, Dirk Cattrysse, Joost R. Duflou · Lirias · 2009
In a knowledge-driven world confronted with vast information overload, well-optimized retrieval of relevant information has become increasingly important. Document management systems often deal with large collections of documents, many of which reuse parts of other documents. This results in the usage of unnecessary disk space as well as the existence of documents containing nearly the same content but without reference to each other. The authors suggest an approach in which a document is treated as an array of pointers to coherent pieces of text, here called subtexts. A subtext is coherent if it is related to a single topic. The performance of document management systems in terms of, for instance, search speed could be significantly increased if redundant subtexts can be identified and deleted, and documents can be constructed by referring to the same pool of subtexts. This paper presents a set of techniques to automatically identify these (near) duplicates of subtexts. To identify these duplicates a document is first subdivided in coherent document subtexts related to their topics. These techniques are based on stem or term chains linking document entities, such as sentences or paragraphs, based on the reoccurrences of stems or terms. The number and positions of these reoccurrences in the document are used in a weighting function to quantify the coherence of a document. Applying this function on a document results in a coherence graph of the document linking its entities. Graph partitioning techniques based on the spectral properties of the coherence graph are used to divide this graph into a number of subtexts. The most suitable number of subtexts is determined by resorting the document entities based on the order explained by the eigenvector of the second largest eigenvector. The resulting subtexts are an aggregation of (not necessarily adjacent) entities. A comparison function based on the coherence graph and the term chains are used to quantify the duplicate relationship between two documents. This function can be executed on the complete documents or the extracted subtexts to retrieve the near-duplicate documents. Therefore the technique is capable to not only identify near-duplicate documents of similar length, but also reused small subtexts in larger documents. Performance tests are conducted in test environments based on books of the Gutenberg project to prove the technique's capabilities. The relevance of these techniques for knowledge management is further explained.