Bursty and hierarchical structure in streams
The DOI matches its Crossref record; 63 of the 65 references it cites were found in a registry or an index.
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; in some ways, 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.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“Prior work has explored burst detection methods to identify sudden increases in attention over time (He & Parker, 2010;Kleinberg, 2002;Tattershall et al., 2020)”
From Identifying and evaluating emerging scientific trends through temporal n-gram analysis (2026) · cites this paper as Kleinberg, 2002
In the citing paper
“A model from Kleinberg (2002) uses a probabilistic automaton to identify sustained periods of unusually high frequency and reveal their underlying hierarchical structure.”
From Identifying and evaluating emerging scientific trends through temporal n-gram analysis (2026) · cites this paper as Kleinberg (2002)
In the citing paper
“Most trend detection systems rely on indirect validation, such as alignment with expert-curated taxonomies or retrospective correlation with later citation counts (Kleinberg, 2002;Tattershall et al., 2020;Wei et al., 2022).”
From Identifying and evaluating emerging scientific trends through temporal n-gram analysis (2026) · cites this paper as Kleinberg, 2002
In the citing paper
“The resulting value s = 5.7 (substantially higher than the s = 2 originally proposed for email-arrival data (Kleinberg, 2002)) reflects the large base rates of quarterly scholarly publication, which require a sharper relative increase to constitute a credible signal of emergence.”
From Identifying and evaluating emerging scientific trends through temporal n-gram analysis (2026) · cites this paper as Kleinberg, 2002
Citations
Cites
A tutorial on hidden Markov models and selected applications in speech recognition
Rabiner, L. R. (1989) · Proceedings of the IEEE · doi:10.1109/5.18626 · Cited by 22,743
Nearest neighbor pattern classification
Cover, T., & Hart, P. (1967) · IEEE Transactions on Information Theory · doi:10.1109/tit.1967.1053964 · Cited by 16,936
Agrawal, R., & Srikant, R. (2002) · Proceedings of the Eleventh International Conference on Data Engineering · doi:10.1109/icde.1995.380415 · Cited by 5,155
The Analysis of Time Series: An Introduction
Dickey, D. A., & Chatfield, C. (1991) · Technometrics · doi:10.2307/1268794 · Cited by 3,525
Story and Discourse: Narrative Structure in Fiction and Film
Austin, T. R., & Chatman, S. (1979) · The Journal of Aesthetics and Art Criticism · doi:10.2307/430732 · Cited by 2,658
Hand, D. J., Mannila, H., & Smyth, P. (2001) · Cited by 2,581
Attention, intentions, and the structure of discourse
Grosz, B. J., & Sidner, C. L. (1986) · doi:10.5555/12457.12458 · Cited by 2,580
Agents that reduce work and information overload
Maes, P. (1994) · Communications of the ACM · doi:10.1145/176789.176792 · Cited by 2,321
The Analysis of Time Series: An Introduction with R
Chatfield, C., & Xing, H. (2019) · Chapman & Hall/CRC eBooks · doi:10.1201/9781351259446 · Cited by 1,803
Principles of mixed-initiative user interfaces
Horvitz, E. (1999) · Proceedings of the SIGCHI conference on Human factors in computing systems the CHI is the limit - CHI '99 · doi:10.1145/302979.303030 · Cited by 1,490
Research works printed but not linked: 21
- Agrawal R., 1995, Proc. Intl. Conf. on Data Engineering
- Allan J., 1998, DARPA Broadcast News Transcription and Understanding Workshop
- T. Blanton Ed. White House E-mail New Press 1995. T. Blanton Ed. White House E-mail New Press 1995.
- Chatman S., 1978, Cornell Univ. Press
- Cohen W., 1996, AAAI Spring Symp. Machine Learning and Information Access
- Genette G., 1980, Cornell Univ. Press
- G. Genette Narrative Discourse Revisited English translation (J.E. Lewin) Cornell Univ. Press 1988. G. Genette Narrative Discourse Revisited English translation (J.E. Lewin) Cornell Univ. Press 1988.
- Han J., 1998, Proc. Intl. Conf. Knowledge Discovery and Data Mining
- 10.5555/857190.857680 · doi:10.5555/857190.857680
- Kelly F. P., 1996, Press
- Keogh E., 1997, Intl. Conf. Knowledge Discovery and Data Mining
- Lavrenko V., 2000, KDD-2000 Workshop on Text Mining
- Mannila H., 1995, Intl. Conf. on Knowledge Discovery and Data Mining
- Martin R., 2001, Temporal Data Mining
- Miller N., 1998, IEEE Visualization
- Redmond M., 1998, AAAI Workshop on Case-Based Reasoning
- Rennie J., 2000, KDD Workshop on Text Mining
- Sahami M., 1998, AAAI Workshop on Learning for Text Categorization
- B. Schneier Applied Cryptography Wiley 1996. B. Schneier Applied Cryptography Wiley 1996.
- Segal R., 2000, Proc. Intl. Conf. on Machine Learning
- Wong P., 2000, IEEE Information Visualization
Cited by
Chen, C. (2006) · Journal of the American Society for Information Science and Technology · doi:10.1002/asi.20317 · Cited by 6,433
Statistical physics of social dynamics
Castellano, C., Fortunato, S., & Loreto, V. (2009) · Reviews of Modern Physics · doi:10.1103/revmodphys.81.591 · Cited by 4,119
The origin of bursts and heavy tails in human dynamics
Barabási, A.-L. (2005) · Nature · doi:10.1038/nature03459 · Cited by 2,210
Science Mapping: A Systematic Review of the Literature
Chen, C. (2017) · Journal of Data and Information Science · doi:10.1515/jdis-2017-0006 · Cited by 1,925
Group formation in large social networks: membership, growth, and evolution
Backstrom, L., Huttenlocher, D., Kleinberg, J., & Lan, X. (2006) · Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1150402.1150412 · Cited by 1,805
Self-citation
Metadata
- Authors
- Kleinberg, J.
- Affiliations
- Cornell University (US)
- Corresponding author
- Kleinberg, Jon
- ORCID
- Kleinberg, Jon
- Venue
- Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining
- Publisher
- ACM
- Published
- 2002-07-23
- Pages
- 91-101
- OpenAlex
- W2026302857
- Cited by
- 1,337
- References
- 65
- Citations by year
- 2026: 101 · 2025: 68 · 2024: 63 · 2023: 77 · 2022: 43 · 2021: 44 · 2020: 45 · 2019: 41 · 2018: 58 · 2017: 61 · 2016: 59 · 2015: 92 · 2014: 73 · 2013: 81 · 2012: 70
- FWCI
- 19.27
- Type
- conference paper
- Language
- en
- Open access
- closed
- Locations
- ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) (publishedVersion)
- eCommons (Cornell University) (submittedVersion)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Advanced Text Analysis Techniques
- Physical Sciences › Computer Science › Artificial Intelligence › Topic Modeling
- Social Sciences › General Social Sciences › Computational and Text Analysis Methods
- Keywords
- document streams, burst detection, hierarchy, state transitions, email, topic emergence
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.