Technical Reports


Click here for full text: PDF

Applying Syntactic Similarity Algorithms for Enterprise Information Management

Cherkasova, Ludmila; Eshghi, Kave; Morrey III, Charles B.; Tucek, Joseph; Veitch, Alistair
HP Laboratories


Keyword(s): syntActic similarity, enterprise information management, performance modeling, shingling algorithms, content-based chunking algorithms.

Abstract: For implementing content management solutions and enabling new applications associated with data retention, regulatory compliance, and litigation issues, enterprises need to develop advanced analytics to uncover relationships among the documents, e.g., content similarity, provenance, and clustering. In this paper, we evaluate the performance of four syntactic similarity algorithms. Three algorithms are based on Broder's "shingling" technique while the fourth algorithm employs a more recent approach, "content-based chunking". For our experiments, we use a specially designed corpus of documents that includes a set of "similar" documents with a controlled number of modifications. Our performance study reveals that the similarity metric of all four algorithms is highly sensitive to settings of the algorithms' parameters: sliding window size and fingerprint sampling frequency. We identify a useful range of these parameters for achieving good practical results, and compare the performance of the four algorithms in a controlled environment. We validate our results by applying these algorithms to finding near duplicates in two large collections of HP technical support documents.

9 Pages

Additional Publication Information: To be published in Proceedings of the 15th ACM SIGKDD conference on Knowledge Discovery and Data Mining, 2009.

External Posting Date: May 6, 2009 [Fulltext]. Approved for External Publication
Internal Posting Date: May 6, 2009 [Fulltext]

Back to Index