Resource-adaptive real-time new event detection

ABSTRACT

In a document streaming environment, online detection of the first documents that mention previously unseen events is an open challenge. For this online new event detection (ONED) task, existing studies usually assume that enough resources are always available and focus entirely on detection accuracy without considering efficiency. Moreover, none of the existing work addresses the issue of providing an effective and friendly user interface. As a result, there is a significant gap between the existing systems and a system that can be used in practice. In this paper, we propose an ONED framework with the following prominent features. First, a combination of indexing and compression methods is used to improve the document processing rate by orders of magnitude without sacrificing much detection accuracy. Second, when resources are tight, a resource-adaptive computation method is used to maximize the benefit that can be gained from the limited resources. Third, when the new event arrival rate is beyond the processing capability of the consumer of the ONED system, new events are further filtered and prioritized before they are presented to the consumer. Fourth, implicit citation relationships are created among all the documents and used to compute the importance of document sources. This importance information can guide the selection of document sources. We implemented a prototype of our framework on top of IBM's Stream Processing Core middleware. We also evaluated the effectiveness of our techniques on the standard TDT5 benchmark. To the best of our knowledge, this is the first implementation of a real application in a large-scale stream processing system.

REFERENCES

• 1: James Allan , Rahul Gupta , Vikas Khandelwal, Temporal summaries of new topics, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.10-18, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383954]
• 2: James Allan , Victor Lavrenko , Hubert Jin, First story detection in TDT is hard, Proceedings of the ninth international conference on Information and knowledge management, p.374-381, November 06-11, 2000, McLean, Virginia, United States [doi>10.1145/354756.354843]
• 3: James Allan , Ron Papka , Victor Lavrenko, On-line new event detection and tracking, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.37-45, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290954]
• 4: James Allan , Courtney Wade , Alvaro Bolivar, Retrieval and novelty detection at the sentence level, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada [doi>10.1145/860435.860493]
• 5: Andrew Arnt , Shlomo Zilberstein , James Allan , Abdel-Illah Mouaddib, Dynamic Composition of Information Retrieval Techniques, Journal of Intelligent Information Systems, v.23 n.1, p.67-97, July 2004 [doi>10.1023/B:JIIS.0000029671.27333.7d]
• 6: K. Bharat, A. Z. Broder, and J. Dean et al. A Comparison of Techniques to Find Mirrored Hosts on the WWW. IEEE Data Eng. Bull. 23(4): 21--26, 2000.
• 7: Thorsten Brants , Francine Chen, A System for new event detection, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada [doi>10.1145/860435.860495]
• 8: R. Braun, R. Kaneshiro. Exploiting Topic Pragmatics for New Event Detection in TDT-2004. TDT-2004 Workshop.
• 9: Andrei Z. Broder, Identifying and Filtering Near-Duplicate Documents, Proceedings of the 11th Annual Symposium on Combinatorial Pattern Matching, p.1-10, June 21-23, 2000
• 10: 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]
• 11: F. Chen, A. Farahat, and T. Brants. Story Link Detection and New Event Detection are Asymmetric. HLT-NAACL 2003.
• 12: G.M. Corso, A. Gulli, and F. Romani. Ranking a Stream of News. WWW 2005: 97--106.
• 13: M. Clayton. US Plans Massive Data Sweep. The Christian Science Monitor, February 09, 2006. http://www.csmonitor.com/2006/0209/p01s02-uspo.html, 2006.
• 14: J. Cho, N. Shivakumar, and H. Garcia-Molina. Finding Replicated Web Collections. SIGMOD Conf. 2000: 355--366.
• 15: David DeWitt , Jim Gray, Parallel database systems: the future of high performance database systems, Communications of the ACM, v.35 n.6, p.85-98, June 1992 [doi>10.1145/129888.129894]
• 16: Google News Homepage. http://news.google.com, 2006.
• 17: Navendu Jain , Lisa Amini , Henrique Andrade , Richard King , Yoonho Park , Philippe Selo , Chitra Venkatramani, Design, implementation, and evaluation of the linear road bnchmark on the stream processing core, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142522]
• 18: Theodore Johnson , Dennis Shasha, 2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm, Proceedings of the 20th International Conference on Very Large Data Bases, p.439-450, September 12-15, 1994
• 19: Giridhar Kumaran , James Allan, Text classification and named entities for new event detection, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom [doi>10.1145/1008992.1009044]
• 20: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Journal of the ACM (JACM), v.46 n.5, p.604-632, Sept. 1999 [doi>10.1145/324133.324140]
• 21: Xiaoyan Li , W. Bruce Croft, Novelty detection based on sentence level patterns, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany [doi>10.1145/1099554.1099734]
• 22: E. Lipton. Software to Monitor Overseas Opinions of U.S. The New York Times, October 4, 2006. http://news.zdnet.com/2100--9588_22--6122641.html, 2006.
• 23: Zhiwei Li , Bin Wang , Mingjing Li , Wei-Ying Ma, A probabilistic model for retrospective news event detection, 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.1076055]
• 24: Christopher D. Manning , Hinrich Schütze, Foundations of statistical natural language processing, MIT Press, Cambridge, MA, 1999
• 25: L. Page, S. Brin, and R. Motwani et al. The PageRank Citation Ranking: Bringing Order to the Web. Technical report, Stanford Digital Library Technologies Project, 1998.
• 26: M. F. Porter. An Algorithm for Suffix Stripping. Program 14(3): 130--137, 1980.
• 27: Michael Persin , Justin Zobel , Ron Sacks-Davis, Filtered document retrieval with frequency-sorted indexes, Journal of the American Society for Information Science, v.47 n.10, p.749-764, Oct. 1996 [doi>10.1002/(SICI)1097-4571(199610)47:10<749::AID-ASI3>3.3.CO;2-U]
• 28: S. E. Robertson, S. Walker, and M. Hancock-Beaulieu. Okapi at TREC-7: Automatic Ad Hoc, Filtering, VLC and Interactive. TREC 1998: 199--210.
• 29: Nicola Stokes , Joe Carthy, Combining semantic and syntactic document classifiers to improve first story detection, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.424-425, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.384068]
• 30: A. Singhal. Modern Information Retrieval: A Brief Overview. IEEE Data Eng. Bull. 24(4): 35--43, 2001.
• 31: Tetsuya Sakai , Karen Sparck-Jones, Generic summaries for indexing in information retrieval, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.190-198, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383987]
• 32: SMART Stopword List. http://www.lextek.com/manuals/onix/stopwords2.html, 2005.
• 33: C. Tang, S. Dwarkadas. Hybrid Global-Local Indexing for Efficient Peer-to-Peer Information Retrieval. NSDI 2004: 211--224.
• 34: TDT Homepage. http://www.nist.gov/speech/tests/tdt.
• 35: TREC Novelty Track. http://trec.nist.gov/tracks.html, 2004.
• 36: Yahoo! News Homepage. http://news.yahoo.com, 2006.
• 37: Yiming Yang , Tom Pierce , Jaime Carbonell, A study of retrospective and on-line event detection, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.28-36, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290953]
• 38: Yiming Yang , Jian Zhang , Jaime Carbonell , Chun Jin, Topic-conditioned novelty detection, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775150]
• 39: Yi Zhang , Jamie Callan , Thomas Minka, Novelty and redundancy detection in adaptive filtering, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, August 11-15, 2002, Tampere, Finland [doi>10.1145/564376.564393]
• 40: Yi-Cheng Tu , Song Liu , Sunil Prabhakar , Bin Yao, Load shedding in stream databases: a control-based approach, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea

INDEX TERMS

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

General Terms:
Algorithms, Experimentation

Keywords:
document streaming, online new event detection