The DOI matches its Crossref record; 38 of the 38 references it cites were found in a registry or an index.
Probabilistic discovery of time series motifs
Abstract
Several important time series data mining problems reduce to the core task of finding approximately repeated subsequences in a longer time series. In an earlier work, we formalized the idea of approximately repeated subsequences by introducing the notion of time series motifs. Two limitations of this work were the poor scalability of the motif discovery algorithm, and the inability to discover motifs in the presence of noise.Here we address these limitations by introducing a novel algorithm inspired by recent advances in the problem of pattern discovery in biosequences. Our algorithm is probabilistic in nature, but as we show empirically and theoretically, it can find time series motifs with very high probability even in the presence of noise or "don't care" symbols. Not only is the algorithm fast, but it is an anytime algorithm, producing likely candidate motifs almost immediately, and gradually improving the quality of results over time.
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
Lecture Notes in Artificial Intelligence
Brézillon, P., & Bouquet, P. (1999) · Cited by 7,473
Biological sequence analysis probabilistic models of proteins and nucleic acids
Durbin, R. M., Eddy, S. R., Krogh, A., & Mitchison, G. (1998) · Cited by 3,565
Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids
Durbin, R., Eddy, S. R., Krogh, A., & Mitchison, G. (1998) · Cambridge University Press eBooks · doi:10.1017/cbo9780511790492 · Cited by 3,246
(1999) · Cited by 3,186
Detecting Subtle Sequence Signals: a Gibbs Sampling Strategy for Multiple Alignment
Lawrence, C. E., Altschul, S. F., Boguski, M. S., Liu, J. S., Neuwald, A. F., & Wootton, J. C. (1993) · Science · doi:10.1126/science.8211139 · Cited by 1,807
Dimensionality Reduction for Fast Similarity Search in Large Time Series Databases
Keogh, E., Chakrabarti, K., Pazzani, M., & Mehrotra, S. (2001) · Knowledge and Information Systems · doi:10.1007/pl00011669 · Cited by 1,573
Self-citationDiscovering similar multidimensional trajectories
Vlachos, M., Kollios, G., & Gunopulos, D. (2003) · Proceedings 18th International Conference on Data Engineering · doi:10.1109/icde.2002.994784 · Cited by 1,468
Hertz, G. Z., & Stormo, G. D. (1999) · Bioinformatics · doi:10.1093/bioinformatics/15.7.563 · Cited by 1,243
Efficient time series matching by wavelets
Chan, K.-P., & Fu, A. W.-C. (1999) · Proceedings 15th International Conference on Data Engineering (Cat. No.99CB36337) · doi:10.1109/icde.1999.754915 · Cited by 1,031
van Helden, J., André, B., & Collado-Vides, J. (1998) · Journal of Molecular Biology · doi:10.1006/jmbi.1998.1947 · Cited by 741
Unsupervised learning of multiple motifs in biopolymers using expectation maximization
Bailey, T. L., & Elkan, C. (1995) · Machine Learning · doi:10.1007/bf00993379 · Cited by 670
Fast Time Sequence Indexing for Arbitrary Lp Norms
Yi, B.-K., & Faloutsos, C. (2018) · doi:10.1184/r1/6605618 · Cited by 650
Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases
Agrawal, R., Lin, K.-I., Sawhney, H., & Shim, K. (1995) · Cited by 649
Rule discovery from time series
Das, G., Lin, K.-I., Mannila, H., Renganathan, G., & Smyth, P. (1998) · Cited by 637
Efficient mining of partial periodic patterns in time series database
Han, J., Dong, G., & Yin, Y. (1999) · Proceedings 15th International Conference on Data Engineering (Cat. No.99CB36337) · doi:10.1109/icde.1999.754913 · Cited by 587
Combinatorial pattern discovery in biological sequences: The TEIRESIAS algorithm.
Rigoutsos, I., & Floratos, A. (1998) · Bioinformatics · doi:10.1093/bioinformatics/14.1.55 · Cited by 557
Combinatorial approaches to finding subtle signals in DNA sequences.
Pevzner, P. A., & Sze, S. (2000) · PubMed · Cited by 549
Finding Motifs Using Random Projections
Buhler, J., & Tompa, M. (2002) · Journal of Computational Biology · doi:10.1089/10665270252935430 · Cited by 532
Lawrence, C. E., & Reilly, A. A. (1990) · Proteins: Structure, Function, and Bioinformatics · doi:10.1002/prot.340070105 · Cited by 526
Keogh, E., & Pazzani, M. J. (1998) · Cited by 496
Self-citationLin, J. (2002) · Cited by 460
On the need for time series data mining benchmarks: a survey and empirical demonstration
Keogh, E., & Kasetty, S. (2002) · Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/775047.775062 · Cited by 442
Self-citationScargle, J. D. (1998) · The Astrophysical Journal · doi:10.1086/306064 · Cited by 398
Efficient large-scale sequence comparison by locality-sensitive hashing
Buhler, J. (2001) · Bioinformatics · doi:10.1093/bioinformatics/17.5.419 · Cited by 259
Probabilistic and Statistical Properties of Words: An Overview
Reinert, G., Schbath, S., & Waterman, M. S. (2000) · Journal of Computational Biology · doi:10.1089/10665270050081360 · Cited by 245
Identifying Representative Trends in Massive Time Series Data Sets Using Sketches
Indyk, P., Koudas, N., & Muthukrishnan, S. (2000) · Very Large Data Bases · Cited by 208
Proceedings 14th International Conference on Data Engineering
(1998) · Proceedings 14th International Conference on Data Engineering · doi:10.1109/icde.1998.655751 · Cited by 180
Deformable Markov model templates for time-series pattern matching
Ge, X., & Smyth, P. (2000) · Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/347090.347109 · Cited by 178
Locality-preserving hashing in multidimensional spaces
Indyk, P., Motwani, R., Raghavan, P., & Vempala, S. (1997) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/258533.258656 · Cited by 167
Finding motifs using random projections
Buhler, J., & Tompa, M. (2001) · Proceedings of the fifth annual international conference on Computational biology · doi:10.1145/369133.369172 · Cited by 165
Discovery of Temporal Patterns. Learning Rules about the Qualitative Behaviour of Time Series
Höppner, F. (2001) · European Conference on Principles of Data Mining and Knowledge Discovery · doi:10.1007/3-540-44794-6_16 · Cited by 152
Kok, J. N., Koronacki, J., de Mántaras, R. L., Matwin, S., Mladenić, D., & Skowron, A. (2007) · Cited by 110
An Updated Bibliography of Temporal, Spatial, and Spatio-temporal Data Mining Research
Roddick, J. F., Hornsby, K., & Spiliopoulou, M. (2001) · Lecture notes in computer science · doi:10.1007/3-540-45244-3_12 · Cited by 103
Methods for discovering novel motifs in nucleic acid sequences
Staden, R. (1989) · Computer applications in the biosciences · doi:10.1093/bioinformatics/5.4.293 · Cited by 93
Monotony of Surprise and Large-Scale Quest for Unusual Words
Apostolico, A., Bock, M. E., & Lonardi, S. (2003) · Journal of Computational Biology · doi:10.1089/10665270360688020 · Cited by 81
Self-citationA Method for Clustering the Experiences of a Mobile Robot that Accords with Human Judgments
Oates, T., Schmill, M. D., & Cohen, P. R. (2000) · Cited by 75
Monotony of surprise and large-scale quest for unusual words
Apostolico, A., Bock, M. E., & Lonardi, S. (2002) · doi:10.1145/565196.565200 · Cited by 41
Self-citationHypothesis Generation Strategies for Adaptive Problem Solving
Engelhardt, B. E., Chien, S., & Mutz, D. H. (2000) · Cited by 2
Cited by
Time-series clustering – A decade review
Aghabozorgi, S., Seyed Shirkhorshidi, A., & Ying Wah, T. (2015) · Information Systems · doi:10.1016/j.is.2015.04.007 · Cited by 1,826
Experiencing SAX: A novel symbolic representation of time series
Lin, J., Keogh, E., Wei, L., & Lonardi, S. (2007) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-007-0064-z · Cited by 1,618
Self-citationA review on time series data mining
Fu, T.-C. (2011) · Engineering Applications of Artificial Intelligence · doi:10.1016/j.engappai.2010.09.007 · Cited by 1,500
Esling, P., & Agon, C. (2012) · ACM Computing Surveys · doi:10.1145/2379776.2379788 · Cited by 997
Time series shapelets: a new primitive for data mining
Ye, L., & Keogh, E. (2009) · Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1557019.1557122 · Cited by 987
Self-citation
Metadata
- Authors
- Chiu, B., Keogh, E., & Lonardi, S.
- Venue
- Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining
- Publisher
- ACM
- Published
- 2003-08-24
- Pages
- 493-498
- OpenAlex
- W2006761268
- Cited by
- 573
- References
- 38
- FWCI
- 19.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.