Time-dependent event hierarchy construction

ABSTRACT

In this paper, an algorithm called Time Driven Documents-partition (TDD) is proposed to construct an event hierarchy in a text corpus based on a given query. Specifically, assume that a query contains only one feature - Election. Election is directly related to the events such as 2006 US Midterm Elections Campaign, 2004 US Presidential Election Campaign and 2004 Taiwan Presidential Election Campaign, where these events may further be divided into several smaller events (e.g. the 2006 US Midterm Elections Campaign can be broken down into events such as campaign for vote, election results and the resignation of Donald H. Rumsfeld). As such, an event hierarchy is resulted. Our proposed algorithm, TDD, tackles the problem by three major steps: (1)Identify the features that are related to the query according to both the timestamps and the contents of the documents. The features identified are regarded as bursty features; (2) Extract the documents that are highly related to the bursty features based on time; (3) Partition the extracted documents to form events and organize them in a hierarchicalstructure. To the best of our knowledge, there is little works targeting for constructing a feature-based event hierarchy for a text corpus. Practically, event hierarchies can assist us to efficiently locate our target information in a text corpus easily. Again, assume that Election is used for a query. Without an event hierarchy, it is very difficult to identify what are the major events related to it, when do these events happened, as well as the features and the news articles that are related to each of these events. We have archived two-year news articles to evaluate the feasibility of TDD. The encouraging results indicated that TDD is practically sound and highly effective.

REFERENCES

• 1: 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]
• 2: Thorsten Brants , Francine Chen , Ayman Farahat, 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]
• 3: Stanley F. Chen , Joshua Goodman, An empirical study of smoothing techniques for language modeling, Proceedings of the 34th annual meeting on Association for Computational Linguistics, p.310-318, June 24-27, 1996, Santa Cruz, California [doi>10.3115/981863.981904]
• 4: M. Connell, A. Feng, G. Kumaran, H. Raghavan, C. Shah, and J. Allan. UMass at TDT 2004. In 2004 Topic Detection and Tracking Workshop (TDT'04), Gaithersburg, Maryland, USA, 2004.
• 5: W. B. Frakes, Stemming algorithms, Information retrieval: data structures and algorithms, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 6: Gabriel Pui Cheong Fung , Jeffrey X. Yu , Hongjun Lu , Philip S. Yu, Text Classification without Negative Examples Revisit, IEEE Transactions on Knowledge and Data Engineering, v.18 n.1, p.6-20, January 2006 [doi>10.1109/TKDE.2006.16]
• 7: Gabriel Pui Cheong Fung , Jeffrey Xu Yu , Philip S. Yu , Hongjun Lu, Parameter free bursty events detection in text streams, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 8: Barbara J. Grosz , Candace L. Sidner, Attention, intentions, and the structure of discourse, Computational Linguistics, v.12 n.3, p.175-204, July-September 1986
• 9: Jon Kleinberg, Bursty and hierarchical structure in streams, 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.775061]
• 10: Vijay Kumar , Richard Furuta , Robert B. Allen, Metadata visualization for digital libraries: interactive timeline editing and review, Proceedings of the third ACM conference on Digital libraries, p.126-133, June 23-26, 1998, Pittsburgh, Pennsylvania, United States [doi>10.1145/276675.276689]
• 11: David D. Lewis , Kimberly A. Knowles, Threading electronic mail: a preliminary study, Information Processing and Management: an International Journal, v.33 n.2, p.209-217, March 1997 [doi>10.1016/S0306-4573(96)00063-5]
• 12: 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]
• 13: Xia Lin , Dagobert Soergel , Gary Marchionini, A self-organizing semantic map for information retrieval, Proceedings of the 14th annual international ACM SIGIR conference on Research and development in information retrieval, p.262-269, October 13-16, 1991, Chicago, Illinois, United States [doi>10.1145/122860.122887]
• 14: Ye Liu , Hanxiong Chen , Jeffrey Xu Yu , Nobuo Ohbo, Using Stem Rules to Refine Document Retrieval Queries, Proceedings of the Third International Conference on Flexible Query Answering Systems, p.248-259, May 13-15, 1998
• 15: J. B. Lovins. Development of a stemming algorithm. Mechanical Traqnslation and Computational Linguistics, 11:22--31, 1968.
• 16: Sofus A. Macskassy , Foster Provost, Intelligent information triage, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.318-326, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.384015]
• 17: Qiaozhu Mei , ChengXiang Zhai, Discovering evolutionary theme patterns from text: an exploration of temporal text mining, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081895]
• 18: Xuerui Wang , Andrew McCallum, Topics over time: a non-Markov continuous-time model of topical trends, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150450]
• 19: D. C. Montogomery and G. C. Runger. Applied Statistics and Probability for Engineers. John Wiley & Sons, Inc., second edition, 1999.
• 20: Satoshi Morinaga , Kenji Yamanishi, Tracking dynamics of topic trends using a finite mixture model, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1016919]
• 21: R. Papka , J. Allan, On-Line New Event Detection using Single Pass Clustering TITLE2:, University of Massachusetts, Amherst, MA, 1998
• 22: H. J. Peat and P. Willett. The limitations of term co-occurrence data for query expansion in document retrieval systems. Journal of the American Society for Information Science (JASIS), 41(4):378--383, 1991.
• 23: Earl Rennison, Galaxy of news: an approach to visualizing and understanding expansive news landscapes, Proceedings of the 7th annual ACM symposium on User interface software and technology, p.3-12, November 02-04, 1994, Marina del Rey, California, United States [doi>10.1145/192426.192429]
• 24: Gerard Salton , Christopher Buckley, Term-weighting approaches in automatic text retrieval, Information Processing and Management: an International Journal, v.24 n.5, p.513-523, 1988 [doi>10.1016/0306-4573(88)90021-0]
• 25: G. Salton and C. Buckley. Improving retrieval performance by relevance feedback. Journal of the American Society for Information Science (JASIS), 41(4):288--297, 1990.
• 26: Fabrizio Sebastiani, Machine learning in automated text categorization, ACM Computing Surveys (CSUR), v.34 n.1, p.1-47, March 2002 [doi>10.1145/505282.505283]
• 27: David A. Smith, Detecting and Browsing Events in Unstructured text, 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.564391]
• 28: M. Spitters and W. Kraaij. TNO at TDT2001: Language model-based topic detection. In 2001 Topic Detection and Tracking Workshop (TDT'01), Gaithersburg, Maryland, USA, 2001.
• 29: M. Steinbach, G. Karypis, and V. Kumar. A Comparison of Document Clustering Techniques. In Proceedings of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD'00) Workshop on Text Mining, 2000.
• 30: Russell Swan , James Allan, Extracting significant time varying features from text, Proceedings of the eighth international conference on Information and knowledge management, p.38-45, November 02-06, 1999, Kansas City, Missouri, United States [doi>10.1145/319950.319956]
• 31: Russell Swan , James Allan, Automatic generation of overview timelines, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.49-56, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345546]
• 32: D. Trieschnigg and W. Kraaij. Hierarchical topic detection in large digital news archives. In Proceedings of the 5th Dutch Belgian Information Retrieval workshop, pages 55--62, Utrecht, the Netherlands, 2005.
• 33: Michail Vlachos , Christopher Meek , Zografoula Vagena , Dimitrios Gunopulos, Identifying similarities, periodicities and bursts for online search queries, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007586]
• 34: E. Wiener, J. O. Pedersen, and A. S. Weigend. A neural network approach to topic spotting. In Proceedings of the 4th Annual Symposium on Document Analysis and Information Retrieval (SDAIR'95), pages 317--332, Las Vegas, USA, 1994.
• 35: J. A. Wise , J. J. Thomas , K. Pennock , D. Lantrip , M. Pottier , A. Schur , V. Crow, Visualizing the non-visual: spatial analysis and interaction with information from text documents, Proceedings of the 1995 IEEE Symposium on Information Visualization, p.51, October 30-31, 1995, Atlanta, Georgia
• 36: Yiming Yang , Tom Ault , Thomas Pierce , Charles W. Lattimer, Improving text categorization methods for event tracking, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.65-72, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345550]
• 37: Yiming Yang , Jaime G. Carbonell , Ralf D. Brown , Thomas Pierce , Brian T. Archibald , Xin Liu, Learning Approaches for Detecting and Tracking News Events, IEEE Intelligent Systems, v.14 n.4, p.32-43, July 1999 [doi>10.1109/5254.784083]
• 38: 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]

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.m Miscellaneous

General Terms:
Algorithms, Design, Management

Keywords:
clustering, events, hierarchies, presentation, retrieval, text, time