The DOI matches its Crossref record; 47 of the 47 references it cites were found in a registry or an index.
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; 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
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
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
Finding frequent items in data streams
Charikar, M., Chen, K., & Farach-Colton, M. (2004) · Theoretical Computer Science · doi:10.1016/s0304-3975(03)00400-6 · Cited by 1,278
Forster, E. M. (1927) · University of Michigan Library Repository · Cited by 1,011
Email overload: exploring personal information management of email
Whittaker, S., & Sidner, C. (1996) · Proceedings of the SIGCHI conference on Human factors in computing systems common ground - CHI '96 · doi:10.1145/238386.238530 · Cited by 976
Topic Detection and Tracking Pilot Study Final Report
Allan, J., Carbonell, J., Doddington, G. R., Yamron, J., & Yang, Y. (2018) · doi:10.1184/r1/6626252.v1 · Cited by 939
The hierarchical hidden Markov model: Analysis and applications
Fine, S., Singer, Y., & Tishby, N. (1998) · Machine Learning · doi:10.1023/a:1007469218079 · Cited by 906
A study of retrospective and on-line event detection
Yang, Y., Pierce, T., & Carbonell, J. (1998) · Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval · doi:10.1145/290941.290953 · Cited by 731
Kelly, F. P. (1996) · doi:10.1093/oso/9780198523994.003.0008 · Cited by 704
Statistical Models for Text Segmentation
Beeferman, D., Berger, A., & Lafferty, J. (1999) · Machine Learning · doi:10.1023/a:1007506220214 · Cited by 680
On-Line New Event Detection and Tracking
Allan, J., Papka, R., & Lavrenko, V. (2017) · ACM SIGIR Forum · doi:10.1145/3130348.3130366 · Cited by 646
Discovering Frequent Episodes in Sequences.
Mannila, H., Toivonen, H. T. T., & Verkamo, A. I. (1995) · Knowledge Discovery and Data Mining · Cited by 590
On-line new event detection and tracking
Allan, J., Papka, R., & Lavrenko, V. (1998) · Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval · doi:10.1145/290941.290954 · Cited by 530
Event detection from time series data
Guralnik, V., & Srivastava, J. (1999) · Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/312129.312190 · Cited by 474
Fitting Segmented Curves Whose Join Points Have to Be Estimated
Hudson, D. J. (1966) · Journal of the American Statistical Association · doi:10.1080/01621459.1966.10482198 · Cited by 426
ThemeRiver: visualizing theme changes over time
Havre, S., Hetzler, B., & Nowell, L. (2002) · IEEE Symposium on Information Visualization 2000. INFOVIS 2000. Proceedings · doi:10.1109/infvis.2000.885098 · Cited by 416
Learning Rules that Classify E-Mail
Cohen, W. W. (1996) · Cited by 406
Markus, M. L. (1994) · ACM Transactions on Information Systems · doi:10.1145/196734.196738 · Cited by 310
A probabilistic approach to fast pattern matching in time series databases
Keogh, E., & Smyth, P. (1997) · Knowledge Discovery and Data Mining · Cited by 254
Automatic generation of overview timelines
Swan, R., & Allan, J. (2000) · Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval · doi:10.1145/345508.345546 · Cited by 241
Linear-time inference in Hierarchical HMMs
Murphy, K. P., & Paskin, M. A. (2001) · Cited by 183
MailCat: an intelligent assistant for organizing e-mail
Segal, R. B., & Kephart, J. O. (1999) · Proceedings of the third annual conference on Autonomous Agents · doi:10.1145/301136.301209 · Cited by 164
The Effects of Wireless Computing in Collaborative Learning Environments
Gay, G. K., Stefanone, M. A., Grace-Martin, M., & Hembrooke, H. A. (2001) · International Journal of Human-Computer Interaction · doi:10.1207/s15327590ijhc1302_10 · Cited by 152
Threading electronic mail: A preliminary study
Lewis, D. D., & Knowles, K. A. (1997) · Information Processing & Management · doi:10.1016/s0306-4573(96)00063-5 · Cited by 151
Querying and Mining Data Streams: You Only Get One Look.
Garofalakis, M., & Gehrke, J. E. (2002) · Very Large Data Bases · Cited by 149
Concept features in Re:Agent, an intelligent Email agent
Boone, G. (1998) · doi:10.1145/280765.280791 · Cited by 120
ifile: An Application of Machine Learning to E-Mail Filtering
Rennie, J. D. M. (2000) · Cited by 117
TimeMines : Constructing Timelines with Statistical Models of Word Usage
Swan, R. C. (2000) · Cited by 111
Point Estimation of the Parameters of Piecewise Regression Models
Hawkins, D. M. (1976) · Applied Statistics · doi:10.2307/2346519 · Cited by 103
Extracting significant time varying features from text
Swan, R. C., & Allan, J. (1999) · ACM International Conference on Information and Knowledge Management (CIKM) · doi:10.1145/319950.319956 · Cited by 96
Web Browsing, Mobile Computing and Academic Performance
Grace-Martin, M. (2001) · Educational Technology & Society · Cited by 92
Incremental Learning in SwiftFile
Segal, R. B., & Kephart, J. O. (2000) · International Conference on Machine Learning · Cited by 89
Interface agents that learn an investigation of learning issues in a mail agent interface
Payne, T. R., & Edwards, P. J. (1997) · Applied Artificial Intelligence · doi:10.1080/088395197118325 · Cited by 79
Representation of Random Waveforms by Relational Trees
Ehrich, & Foith (1976) · IEEE Transactions on Computers · doi:10.1109/tc.1976.1674681 · Cited by 74
Email—the good, the bad, and the ugly
Berghel, H. (1997) · Communications of the ACM · doi:10.1145/248448.248450 · Cited by 61
Collection-Based Persistent Digital Archives - Part 1
Moore, R., Baru, C., Rajasekar, A., Ludaescher, B., Marciano, R. J., Wan, M., Schroeder, W., & Gupta, A. (2000) · D-Lib Magazine · doi:10.1045/march2000-moore-pt1 · Cited by 57
Scott, S. L., & Smyth, P. (2003) · Oxford University Press eBooks · doi:10.1093/oso/9780198526155.003.0047 · Cited by 57
Finding simple intensity descriptions from event sequence data
Mannila, H., & Salmenkivi, M. (2001) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/502512.502562 · Cited by 23
Collection-Based Persistent Digital Archives - Part 2
Moore, R., Baru, C., Rajasekar, A., et al. (2000) · D-Lib Magazine · doi:10.1045/april2000-moore-pt2 · Cited by 20
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.
- 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,160
- References
- 47
- FWCI
- 17.94
- Type
- conference paper
- Language
- en
- Open access
- closed
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.