Detecting the origin of text segments efficiently

ABSTRACT

In the origin detection problem an algorithm is given a set S of documents, ordered by creation time, and a query document D. It needs to output for every consecutive sequence of k alphanumeric terms in D the earliest document in $S$ in which the sequence appeared (if such a document exists). Algorithms for the origin detection problem can, for example, be used to detect the "origin" of text segments in D and thus to detect novel content in D. They can also find the document from which the author of D has copied the most (or show that D is mostly original.) We concentrate on solutions that use only a fixed amount of memory. We propose novel algorithms for this problem and evaluate them together with a large number of previously published algorithms. Our results show that (1) detecting the origin of text segments efficiently can be done with very high accuracy even when the space used is less than 1% of the size of the documents in $S$, (2) the precision degrades smoothly with the amount of available space, (3) various estimation techniques can be used to increase the performance of the algorithms.

REFERENCES

• 1: R. A. Baeza-Yates, A. R. P. Jr., and N. Ziviani. Understanding content reuse on the web: Static and dynamic analyses. In WEBKDD, pages 227--246, 2006.
• 2: Ricardo Baeza-Yates , Álvaro Pereira , Nivio Ziviani, Genealogical trees on the web: a search engine user perspective, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367548]
• 3: Michael Bendersky , W. Bruce Croft, Finding text reuse on the web, Proceedings of the Second ACM International Conference on Web Search and Data Mining, February 09-12, 2009, Barcelona, Spain [doi>10.1145/1498759.1498835]
• 4: Yaniv Bernstein , Justin Zobel, Redundant documents and search effectiveness, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany [doi>10.1145/1099554.1099733]
• 5: Sergey Brin , James Davis , Héctor García-Molina, Copy detection mechanisms for digital documents, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.398-409, May 22-25, 1995, San Jose, California, United States
• 6: Andrei Z. Broder , Steven C. Glassman , Mark S. Manasse , Geoffrey Zweig, Syntactic clustering of the Web, Selected papers from the sixth international conference on World Wide Web, p.1157-1166, September 1997, Santa Clara, California, United States
• 7: Hung-Chi Chang , Jenq-Haur Wang , Chih-Yi Chiu, Finding Event-Relevant Content from the Web Using a Near-Duplicate Detection Approach, Proceedings of the IEEE/WIC/ACM International Conference on Web Intelligence, p.291-294, November 02-05, 2007 [doi>10.1109/WI.2007.58]
• 8: Dennis Fetterly , Mark Manasse , Marc Najork, On the Evolution of Clusters of Near-Duplicate Web Pages, Proceedings of the First Conference on Latin American Web Congress, p.37, November 10-12, 2003
• 9: Dennis Fetterly , Mark Manasse , Marc Najork, Detecting phrase-level duplication on the world wide web, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil [doi>10.1145/1076034.1076066]
• 10: Monika Henzinger, Finding near-duplicate web pages: a large-scale evaluation of algorithms, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148222]
• 11: Timothy C. Hoad , Justin Zobel, Methods for identifying versioned and plagiarized documents, Journal of the American Society for Information Science and Technology, v.54 n.3, p.203-215, February 1, 2003 [doi>10.1002/asi.10170]
• 12: Udi Manber, Finding similar files in a large file system, Proceedings of the USENIX Winter 1994 Technical Conference on USENIX Winter 1994 Technical Conference, p.2-2, January 17-21, 1994, San Francisco, California
• 13: M. O. Rabin. Fingerprinting by random polynomials. Technidal report, Harvard University, TR-15-81, 1981.
• 14: Saul Schleimer , Daniel S. Wilkerson , Alex Aiken, Winnowing: local algorithms for document fingerprinting, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872770]
• 15: Jangwon Seo , W. Bruce Croft, Local text reuse detection, Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval, July 20-24, 2008, Singapore, Singapore [doi>10.1145/1390334.1390432]
• 16: Narayanan Shivakumar , Hector Garcia-Molina, Finding Near-Replicas of Documents and Servers on the Web, Selected papers from the International Workshop on The World Wide Web and Databases, p.204-212, March 27-28, 1998
• 17: J. Zobel and Y. Bernstein. The case of the duplicate documents measurement, search, and science. In APWeb, pages 26--39, 2006.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.m Miscellaneous

General Terms:
Algorithms, Experimentation, Measurement

Keywords:
document overlap, shingling