Efficient overlap and content reuse detection in blogs and online news articles

ABSTRACT

The use of blogs to track and comment on real world (political, news, entertainment) events is growing. Similarly, as more individuals start relying on the Web as their primary information source and as more traditional media outlets try reaching consumers through alternative venues, the number of news sites on the Web is also continuously increasing. Content-reuse, whether in the form of extensive quotations or content borrowing across media outlets, is very common in blogs and news entries outlets tracking the same real-world event. Knowledge about which web entries re-use content from which others can be an effective asset when organizing these entries for presentation. On the other hand, this knowledge is not cheap to acquire: considering the size of the related space web entries, it is essential that the techniques developed for identifying re-use are fast and scalable. Furthermore, the dynamic nature of blog and news entries necessitates incremental processing for reuse detection. In this paper, we develop a novel qSign algorithm that efficiently and effectively analyze the blogosphere for quotation and reuse identification. Experiment results show that with qSign processing time gains from 10X to 100X are possible while maintaining reuse detection rates of upto 90%. Furthermore, processing time gains can be pushed multiple orders of magnitude (from 100X to 1000X) for 70% recall.

REFERENCES

• 1: David Sifry's Blog. http://www.sifry.com/alerts/.
• 2: Google Blog Search. http://blogsearch.google.com blogsearch.
• 3: Google News. http://news.google.com.
• 4: Google Book Search. http://books.google.com/.
• 5: Yahoo News. http://news.yahoo.com.
• 6: The MD5 Message-Digest Algorithm. http://tools.ietf.org/html/rfc1321.
• 7: WWW'06 Workshop on the Weblogging Ecosystem: Aggregation, Analysis and Dynamics. 2006.
• 8: Eytan Adar , Lada A. Adamic, Tracking Information Epidemics in Blogspace, Proceedings of the 2005 IEEE/WIC/ACM International Conference on Web Intelligence, p.207-214, September 19-22, 2005 [doi>10.1109/WI.2005.151]
• 9: Arvind Arasu , Venkatesh Ganti , Raghav Kaushik, Efficient exact set-similarity joins, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 10: Roberto J. Bayardo , Yiming Ma , Ramakrishnan Srikant, Scaling up all pairs similarity search, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242591]
• 11: Stefan Berchtold , Daniel A. Keim , Hans-Peter Kriegel, The X-tree: An Index Structure for High-Dimensional Data, Proceedings of the 22th International Conference on Very Large Data Bases, p.28-39, September 03-06, 1996
• 12: Y. Bernstein and J. Zobel. A Scalable System for Identifying Co-derivative Documents. In Proceedings of String Processing and Information Retrieval Symp, 2004.
• 13: Rebecca Blood, The Weblog Handbook: Practical Advice on Creating and Maintaining Your Blog, Perseus Publishing, 2002
• 14: A. Broder, On the Resemblance and Containment of Documents, Proceedings of the Compression and Complexity of Sequences 1997, p.21, June 11-13, 1997
• 15: 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
• 16: K. Chakrabarti, and S. Mehrotra. The Hybrid Tree: An Index Structure for High Dimensional Feature Spaces. In ICDE, 1999.
• 17: Surajit Chaudhuri , Venkatesh Ganti , Raghav Kaushik, A Primitive Operator for Similarity Joins in Data Cleaning, Proceedings of the 22nd International Conference on Data Engineering, p.5, April 03-07, 2006 [doi>10.1109/ICDE.2006.9]
• 18: X. Chen, B. Francia, M. Li, and B. Mckinnon. Shared Information and Program Plagiarism Detection. IEEE Transactions on Information Theory, 50 (7), 1545--1551, 2004.
• 19: Yun Chi , Shenghuo Zhu , Xiaodan Song , Junichi Tatemura , Belle L. Tseng, Structural and temporal analysis of the blogosphere through community factorization, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281213]
• 20: R. Cilibrasi, and P. Vitanyi. Clustering by compression. IEEE Transactions on Information Theory, 51(4), 1523--1545, 2005.
• 21: Abdur Chowdhury , Ophir Frieder , David Grossman , Mary Catherine McCabe, Collection statistics for fast duplicate document detection, ACM Transactions on Information Systems (TOIS), v.20 n.2, p.171-191, April 2002 [doi>10.1145/506309.506311]
• 22: Aristides Gionis , Piotr Indyk , Rajeev Motwani, Similarity Search in High Dimensions via Hashing, Proceedings of the 25th International Conference on Very Large Data Bases, p.518-529, September 07-10, 1999
• 23: Luis Gravano , Panagiotis G. Ipeirotis , H. V. Jagadish , Nick Koudas , S. Muthukrishnan , Divesh Srivastava, Approximate String Joins in a Database (Almost) for Free, Proceedings of the 27th International Conference on Very Large Data Bases, p.491-500, September 11-14, 2001
• 24: N. Heintze. Scalable document fingerprinting. In USENIX Workshop on Electronic Commerce, 1996.
• 25: T. Hofmann. Probabilistic latent semantic analysis. In Proceedings of Uncertainty in Artificial Intelligence, 1999.
• 26: Piotr Indyk , Rajeev Motwani , Prabhakar Raghavan , Santosh Vempala, Locality-preserving hashing in multidimensional spaces, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.618-625, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258656]
• 27: Norio Katayama , Shin'ichi Satoh, The SR-tree: an index structure for high-dimensional nearest neighbor queries, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.369-380, May 11-15, 1997, Tucson, Arizona, United States
• 28: Jong Wook Kim , K. Selcuk Candan , Junichi Tatemura, CDIP: Collection-Driven, yet Individuality-Preserving Automated Blog Tagging, Proceedings of the International Conference on Semantic Computing, p.87-94, September 17-19, 2007 [doi>10.1109/ICSC.2007.19]
• 29: J.W. Kim, K.S. Candan, and J.Tatemura. Organization and Tagging of Blog Entries based on Content Reuse. submitted.
• 30: Okan Kolak , Bill N. Schilit, Generating links by mining quotations, Proceedings of the nineteenth ACM conference on Hypertext and hypermedia, June 19-21, 2008, Pittsburgh, PA, USA [doi>10.1145/1379092.1379117]
• 31: 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
• 32: Gurmeet Singh Manku , Arvind Jain , Anish Das Sarma, Detecting near-duplicates for web crawling, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242592]
• 33: Donald Metzler , Yaniv Bernstein , W. Bruce Croft , Alistair Moffat , Justin Zobel, Similarity measures for tracking information flow, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany [doi>10.1145/1099554.1099695]
• 34: 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]
• 35: Sunita Sarawagi , Alok Kirpal, Efficient set joins on similarity predicates, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007652]
• 36: N. Shivakumar and H. Garcia-Molina. SCAM: A Copy Detection Mechanism for Digital Documents. Second Annual Conference on the Theory and Practice of Digital Libraries, 1995.
• 37: 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
• 38: Hui Yang , Jamie Callan, Near-duplicate detection by instance-level constrained clustering, 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.1148243]
• 39: Justin Zobel , Alistair Moffat , Kotagiri Ramamohanarao, Inverted files versus signature files for text indexing, ACM Transactions on Database Systems (TODS), v.23 n.4, p.453-490, Dec. 1998 [doi>10.1145/296854.277632]
• 40: Chuan Xiao , Wei Wang , Xuemin Lin , Jeffrey Xu Yu, Efficient similarity joins for near duplicate detection, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367516]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

General Terms:
Experimentation, Performance

Keywords:
reuse detection, weblogs