Bursty and Hierarchical Structure in Streams

ABSTRACT

A fundamental problem in text data mining is to extract meaningful structure from document streams that arrive continuously over time. E-mail and news articles are two natural examples of such streams, each characterized by topics that appear, grow in intensity for a period of time, and then fade away. The published literature in a particular research field can be seen to exhibit similar phenomena over a much longer time scale. Underlying much of the text mining work in this area is the following intuitive premise—that the appearance of a topic in a document stream is signaled by a “burst of activity,” with certain features rising sharply in frequency as the topic emerges.

The goal of the present work is to develop a formal approach for modeling such “bursts,” in such a way that they can be robustly and efficiently identified, and can provide an organizational framework for analyzing the underlying content. The approach is based on modeling the stream using an infinite-state automaton, in which bursts appear naturally as state transitions; it can be viewed as drawing an analogy with models from queueing theory for bursty network traffic. The resulting algorithms are highly efficient, and yield a nested representation of the set of bursts that imposes a hierarchical structure on the overall stream. Experiments with e-mail and research paper archives suggest that the resulting structures have a natural meaning in terms of the content that gave rise to them.

REFERENCES

• 1: Rakesh Agrawal , Ramakrishnan Srikant, Mining Sequential Patterns, Proceedings of the Eleventh International Conference on Data Engineering, p.3-14, March 06-10, 1995
• 2: Aigrain, P., Zhang, H., and Petkovic, D. 1996. Content-based representation and retrieval of visual media: A state-of-the-art review. Multimedia Tools and Applications, 3.
• 3: Allan, J., Carbonell, J.G., Doddington, G., Yamron, J., and Yang, Y. 1998a. Topic detection and tracking pilot study: Final report. In Proc. DARPA Broadcast News Transcription and Understanding Workshop, Feb.
• 4: 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]
• 5: Anick, D., Mitra, D., and Sondhi, M. 1982. Stochastic theory of a data handling system with multiple sources. Bell Syst. Tech. Journal, 61.
• 6: arxiv.org e-Print archive, at www.arxiv.org.
• 7: Karin Becker , Michelle O. Cardoso , Caren M. Nichele , Michele Frighetto, Mail-by-example: a visual query interface for email management, Proceedings of the working conference on Advanced visual interfaces, p.280-281, May 2000, Palermo, Italy [doi>10.1145/345513.345349]
• 8: Doug Beeferman , Adam Berger , John Lafferty, Statistical Models for Text Segmentation, Machine Learning, v.34 n.1-3, p.177-210, Feb. 1999 [doi>10.1023/A:1007506220214]
• 9: Hal Berghel, Email—the good, the bad, and the ugly, Communications of the ACM, v.40 n.4, p.11-15, April 1997 [doi>10.1145/248448.248450]
• 10: Birrell, A., Perl, S., Schroeder, M., Wobber, T. 1997. The Pachyderm E-mail System, at http://www.research. compaq.com/SRC/pachyderm/.
• 11: Blanton, T. Ed. 1995. White House E-mail. New Press.
• 12: Gary Boone, Concept features in Re:Agent, an intelligent Email agent, Proceedings of the second international conference on Autonomous agents, p.141-148, May 10-13, 1998, Minneapolis, Minnesota, United States [doi>10.1145/280765.280791]
• 13: Moses Charikar , Kevin Chen , Martin Farach-Colton, Finding Frequent Items in Data Streams, Proceedings of the 29th International Colloquium on Automata, Languages and Programming, p.693-703, July 08-13, 2002
• 14: Chatfield, C. 1996. The Analysis of Time Series: An Introduction. Chapman and Hall.
• 15: Chatman, S. 1978. Story and Discourse: Narrative Structure in Fiction and Film. Cornell Univ. Press.
• 16: Chudova, D. and Smyth, P. 2001. Unsupervised identification of sequential patterns under a Markov assumption. KDD Workshop on Temporal Data Mining.
• 17: Cohen, W. 1996. Learning rules that classify e-mail. In Proc. AAAI Spring Symp. Machine Learning and Information Access.
• 18: Cover, T. and Hart, P. 1967. Nearest neighbor pattern classification. IEEE Trans. Information Theory, IT-13:21-27.
• 19: Davison, W., Wall, L., and Barber, S., trn, 1993. http://web.mit.edu/afs/sipb/project/trn/src/trn-3.6/.
• 20: Ehrich, R. and Foith, J. 1976. Representation of random waveforms by relational trees. IEEE Trans. Computers, C25:7.
• 21: Anwar I. Elwalid , Debasis Mitra, Effective bandwidth of general Markovian traffic sources and admission control of high speed networks, IEEE/ACM Transactions on Networking (TON), v.1 n.3, p.329-343, June 1993 [doi>10.1109/90.234855]
• 22: Shai Fine , Yoram Singer , Naftali Tishby, The Hierarchical Hidden Markov Model: Analysis and Applications, Machine Learning, v.32 n.1, p.41-62, July 1998 [doi>10.1023/A:1007469218079]
• 23: Forster, E.M. 1927. Aspects of the Novel. Harcourt, Brace, and World, Inc.
• 24: Gay, G. and Grace-Martin, M. 2001. Web browsing, mobile computing and academic performance. Educational Technology & Society, 4.
• 25: Minos Garofalakis , Johannes Gehrke , Rajeev Rastogi, Querying and mining data streams: you only get one look a tutorial, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564794]
• 26: Genette, G. 1980. Narrative Discourse: An Essay in Method, English translation (J.E. Lewin). Cornell Univ. Press.
• 27: Genette, G. 1988. Narrative Discourse Revisited. English translation (J.E. Lewin). Cornell Univ. Press.
• 28: Google Zeitgeist: Search patterns, trends, and surprises according to Google, at www.google.com/press/ zeitgeist.html.
• 29: 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
• 30: Gruber, T. Hypermail, Enterprise Integration Technologies.
• 31: Valery Guralnik , Jaideep Srivastava, Event detection from time series data, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.33-42, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312190]
• 32: Han, J., Gong, W., and Yin, Y. 1998. Mining segment-wise periodic patterns in time-related databases. In Proc. Intl. Conf. Knowledge Discovery and Data Mining.
• 33: David J. Hand , Padhraic Smyth , Heikki Mannila, Principles of data mining, MIT Press, Cambridge, MA, 2001
• 34: Susan Havre , Beth Hetzler , Lucy Nowell, ThemeRiver: Visualizing Theme Changes over Time, Proceedings of the IEEE Symposium on Information Vizualization 2000, p.115, October 09-10, 2000
• 35: Hawkins, D. 1976. Point estimation of the parameters of piecewise regression models. Applied Statistics, 25.
• 36: Bjoern Heckel , Bernd Hamann, EmVis—a visual e-mail analysis tool, Proceedings of the 1997 workshop on New paradigms in information visualization and manipulation, p.36-38, November 10-14, 1997, Las Vegas, Nevada, United States [doi>10.1145/275519.275527]
• 37: Helfman, J. and Isbell, C. 1995. Ishmail: Immediate identification of important information. AT&T Labs Technical Report.
• 38: Eric Horvitz, Principles of mixed-initiative user interfaces, Proceedings of the SIGCHI conference on Human factors in computing systems: the CHI is the limit, p.159-166, May 15-20, 1999, Pittsburgh, Pennsylvania, United States [doi>10.1145/302979.303030]
• 39: Hudson, D. 1966. Fitting segmented curves whose join points have to be estimated. Journal of the American Statistical Association 61:1097-1129.
• 40: Kelly, F.P. 1996. Notes on effective bandwidths. In Stochastic Networks: Theory and Applications, F.P. Kelly, S. Zachary, and I. Ziedins (Eds.). Oxford Univ. Press.
• 41: Keogh, E. and Smyth, P. 1997. A probabilistic approach to fast pattern matching in time series databases. In Proc. Intl. Conf. Knowledge Discovery and Data Mining.
• 42: Klein, J.I. et al. 2000. Plaintiffs' Memorandum in Support of Proposed Final Judgment, United States of America v. Microsoft Corporation and State of New York, ex rel. Attorney General Eliot Spitzer, et al., v. Microsoft Corporation, Civil Actions No. 98-1232 (TPJ) and 98-1233 (TPJ), April.
• 43: Last, M., Klein, Y., and Kandel, A. 2001. Knowledge discovery in time series databases. IEEE Transactions on Systems, Man, and Cybernetics, 31B.
• 44: Lavrenko, V., Schmill, M., Lawrie, D., Ogilvie, P., Jensen, D., and Allan, J. 2000. Mining of concurrent text and time-series. In KDD-2000 Workshop on Text Mining.
• 45: 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]
• 46: Lukesh, S.S. 1999. E-mail and potential loss to future archives and scholarship, or, The dog that didn't bark. First Monday, 4(9), at http://firstmonday.org.
• 47: Pattie Maes, Agents that reduce work and information overload, Communications of the ACM, v.37 n.7, p.30-40, July 1994 [doi>10.1145/176789.176792]
• 48: Heikki Mannila , Marko Salmenkivi, Finding simple intensity descriptions from event sequence data, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.341-346, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502562]
• 49: Mannila, H., Toivonen, H., and Verkamo, A.I. 1995. Discovering frequent episodes in sequences. In Proc. Intl. Conf. on Knowledge Discovery and Data Mining.
• 50: Martin, R. and Yohai, V. 2001. Data mining for unusual movements in temporal data. KDD Wkshp. Temporal Data Mining.
• 51: M. L. Markus, Finding a happy medium: explaining the negative effects of electronic communication on social life at work, ACM Transactions on Information Systems (TOIS), v.12 n.2, p.119-149, April 1994 [doi>10.1145/196734.196738]
• 52: Nancy E. Miller , Pak Chung Wong , Mary Brewster , Harlan Foote, TOPIC ISLANDS—a wavelet-based text visualization system, Proceedings of the conference on Visualization '98, p.189-196, October 18-23, 1998, Research Triangle Park, North Carolina, United States
• 53: Moore, R., Baru, C., Rajasekar, A., Ludaescher, B., Marciano, R., Wan, M., Schroeder, W., and Gupta, A. 2000. Collection-based persistent digital archives--part 2. D-Lib Magazine, 6.
• 54: Murphy, K. and Paskin, M. 2001. Linear time inference in hierarchical HMMs. Advances in Neural Information Processing Systems (NIPS), 14.
• 55: Olsen, F. 1999. Facing flood of e-mail, archives seeks help from supercomputer researchers. Chronicle of Higher Education, August 24.
• 56: Payne, T. and Edwards, P. 1997. Interface agents that learn: An investigation of learning issues in a mail agent interface. Applied Artificial Intelligence, 11:1-32.
• 57: Stephen Pollock, A rule-based message filtering system, ACM Transactions on Information Systems (TOIS), v.6 n.3, p.232-254, July 1988 [doi>10.1145/45945.214327]
• 58: Rabiner, L. 1989. A tutorial on hidden Markov models and selected applications in speech recognition. In Proc. IEEE, 77.
• 59: Redmond, M. and Adelson, B. 1998. AlterEgo e-mail filtering agent. In Proc. AAAI Workshop on Case-Based Reasoning.
• 60: Rennie, J. 2000. ifile: An application of machine learning to e-mail filtering. In Proc. KDD Workshop on Text Mining.
• 61: Sahami, M., Dumais, S., Heckerman, D., and Horvitz, E. 1998. A bayesian approach to filtering junk email. In Proc. AAAI Workshop on Learning for Text Categorization.
• 62: Schneier, B. 1996. Applied Cryptography Wiley.
• 63: Scott, S.L. 1998. Bayesian Methods and Extensions for the Two State Markov Modulated Poisson Process, Ph.D. Thesis, Harvard University, Dept. of Statistics.
• 64: Scott, S.L. and Smyth, P. 2002. The markov modulated poisson process and markov poisson cascade with applications to web traffic modeling. Seventh Valencia Conference on Bayesian Statistics.
• 65: Richard B. Segal , Jeffrey O. Kephart, MailCat: an intelligent assistant for organizing e-mail, Proceedings of the third annual conference on Autonomous Agents, p.276-282, April 1999, Seattle, Washington, United States [doi>10.1145/301136.301209]
• 66: Richard Segal , Jeffrey O. Kephart, Incremental Learning in SwiftFile, Proceedings of the Seventeenth International Conference on Machine Learning, p.863-870, June 29-July 02, 2000
• 67: Shaw, S. and DeFigueiredo, R. 1990. Structural processing of waveforms as trees. IEEE Transactions on Acoustics, Speech, and Signal Processing, 38:2.
• 68: 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]
• 69: 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]
• 70: Swan, R. and Jensen, D. 2000. TimeMines: Constructing timelines with statistical models of word usage. In KDD-2000 Workshop on Text Mining.
• 71: Steve Whittaker , Candace Sidner, Email overload: exploring personal information management of email, Proceedings of the SIGCHI conference on Human factors in computing systems: common ground, p.276-283, April 13-18, 1996, Vancouver, British Columbia, Canada [doi>10.1145/238386.238530]
• 72: Pak Chung Wong , Wendy Cowley , Harlan Foote , Elizabeth Jurrus , Jim Thomas, Visualizing Sequential Patterns for Text Mining, Proceedings of the IEEE Symposium on Information Vizualization 2000, p.105, October 09-10, 2000
• 73: 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]
• 74: 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.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Markov processes

  I. Computing Methodologies
  I.7 DOCUMENT AND TEXT PROCESSING
      I.7.5 Document Capture
          Subjects: Document analysis

General Terms:
Algorithms, Documentation, Theory

Keywords:
Markov source models, data stream algorithms, text mining