On burstiness-aware search for document sequences

ABSTRACT

As the number and size of large timestamped collections (e.g. sequences of digitized newspapers, periodicals, blogs) increase, the problem of efficiently indexing and searching such data becomes more important. Term burstiness has been extensively researched as a mechanism to address event detection in the context of such collections. In this paper, we explore how burstiness information can be further utilized to enhance the search process. We present a novel approach to model the burstiness of a term, using discrepancy theory concepts. This allows us to build a parameter-free, linear-time approach to identify the time intervals of maximum burstiness for a given term. Finally, we describe the first burstiness-driven search framework and thoroughly evaluate our approach in the context of different scenarios.

REFERENCES

• 1: Deepak Agarwal , Jeff M. Phillips , Suresh Venkatasubramanian, The hunting of the bump: on maximizing statistical discrepancy, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1137-1146, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109683]
• 2: Nilesh Bansal , Nick Koudas, BlogScope: a system for online analysis of high volume text streams, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 3: Nilesh Bansal , Nick Koudas, BlogScope: spatio-temporal analysis of the blogosphere, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242802]
• 4: Bernard Chazelle, The discrepancy method: randomness and complexity, Cambridge University Press, New York, NY, 2000
• 5: Chih-Huai Cheng , Kuan-Yu Chen , Wen-Chin Tien , Kun-Mao Chao, Improved algorithmms for the k maximum-sums problems, Theoretical Computer Science, v.362 n.1, p.162-170, 11 October 2006 [doi>10.1016/j.tcs.2006.06.007]
• 6: Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , Clifford Stein, Introduction to Algorithms, Third Edition, The MIT Press, 2009
• 7: David P. Dobkin , Dimitrios Gunopulos , Wolfgang Maass, Computing the maximum bichromatic discrepancy, with applications to computer graphics and machine learning, Journal of Computer and System Sciences, v.52 n.3, p.453-470, June 1996 [doi>10.1006/jcss.1996.0034]
• 8: David Dobkin , David Eppstein, Computing the discrepancy, Proceedings of the ninth annual symposium on Computational geometry, p.47-52, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.160997]
• 9: Ronald Fagin , Amnon Lotem , Moni Naor, Optimal aggregation algorithms for middleware, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.102-113, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375567]
• 10: 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
• 11: Qi He , Kuiyu Chang , Ee-Peng Lim, Analyzing feature trajectories for event detection, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277779]
• 12: Q. He, K. Chang, E.-P. Lim, and J. Zhang. Bursty feature representation for clustering text streams. In SIAM '07.
• 13: 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]
• 14: Ravi Kumar , Jasmine Novak , Prabhakar Raghavan , Andrew Tomkins, On the bursty evolution of blogspace, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775233]
• 15: National Digital Newspaper Program (NDNP), http://www.loc.gov/ndnp.
• 16: Qi He , Kuiyu Chang , Ee-Peng Lim, Using Burstiness to Improve Clustering of Topics in News Streams, Proceedings of the 2007 Seventh IEEE International Conference on Data Mining, p.493-498, October 28-31, 2007 [doi>10.1109/ICDM.2007.17]
• 17: Walter L. Ruzzo , Martin Tompa, A Linear Time Algorithm for Finding All Maximal Scoring Subsequences, Proceedings of the Seventh International Conference on Intelligent Systems for Molecular Biology, p.234-241, August 06-10, 1999
• 18: 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]
• 19: Yunyue Zhu , Dennis Shasha, Efficient elastic burst detection in data streams, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956789]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Time series analysis

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms

Keywords:
burstiness, document sequences, search