The DOI matches its Crossref record; 37 of the 37 references it cites were found in a registry or an index.
A symbolic representation of time series, with implications for streaming algorithms
Abstract
The parallel explosions of interest in streaming data, and data mining of time series have had surprisingly little intersection. This is in spite of the fact that time series data are typically streaming data. The main reason for this apparent paradox is the fact that the vast majority of work on streaming data explicitly assumes that the data is discrete, whereas the vast majority of time series data is real valued.Many researchers have also considered transforming real valued time series into symbolic representations, nothing that such representations would potentially allow researchers to avail of the wealth of data structures and algorithms from the text processing and bioinformatics communities, in addition to allowing formerly "batch-only" problems to be tackled by the streaming community. While many symbolic representations of time series have been introduced over the past decades, they all suffer from three fatal flaws. Firstly, the dimensionality of the symbolic representation is the same as the original data, and virtually all data mining algorithms scale poorly with dimensionality. Secondly, although distance measures can be defined on the symbolic approaches, these distance measures have little correlation with distance measures defined on the original time series. Finally, most of these symbolic approaches require one to have access to all the data, before creating the symbolic representation. This last feature explicitly thwarts efforts to use the representations with streaming algorithms.In this work we introduce a new symbolic representation of time series. Our representation is unique in that it allows dimensionality/numerosity reduction, and it also allows distance measures to be defined on the symbolic approach that lower bound corresponding distance measures defined on the original series. As we shall demonstrate, this latter feature is particularly exciting because it allows one to run certain data mining algorithms on the efficiently manipulated symbolic representation, while producing identical results to the algorithms that operate on the original data. Finally, our representation allows the real valued data to be converted in a streaming fashion, with only an infinitesimal time and space overhead.We will demonstrate the utility of our representation on the classic data mining tasks of clustering, classification, query by content and anomaly detection.
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
(1994) · Knowledge Discovery and Data Mining · Cited by 3,137
Models and issues in data stream systems
Babcock, B., Babu, S., Datar, M., Motwani, R., & Widom, J. (2002) · Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems · doi:10.1145/543613.543615 · Cited by 2,495
Fast subsequence matching in time-series databases
Faloutsos, C., Ranganathan, M., & Manolopoulos, Y. (1994) · Proceedings of the 1994 ACM SIGMOD international conference on Management of data · doi:10.1145/191839.191925 · Cited by 1,709
Discovering 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
An Introduction to Mathematical Statistics and its Applications.
Skarpness, B., Larsen, R. J., & Marx, M. L. (1983) · Journal of the American Statistical Association · doi:10.2307/2287143 · Cited by 1,149
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
Locally adaptive dimensionality reduction for indexing large time series databases
Keogh, E., Chakrabarti, K., Pazzani, M., & Mehrotra, S. (2001) · Proceedings of the 2001 ACM SIGMOD international conference on Management of data · doi:10.1145/375663.375680 · Cited by 866
Self-citationOn the Need for Time Series Data Mining Benchmarks: A Survey and Empirical Demonstration
Keogh, E., & Kasetty, S. (2003) · Data Mining and Knowledge Discovery · doi:10.1023/a:1024988512476 · Cited by 861
Self-citationFast Time Sequence Indexing for Arbitrary Lp Norms
Yi, B.-K., & Faloutsos, C. (2018) · doi:10.1184/r1/6605618 · Cited by 650
Guha, S., Mishra, N., Motwani, R., & O'Callaghan, L. (2002) · Proceedings 41st Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2000.892124 · Cited by 623
Finding Motifs Using Random Projections
Buhler, J., & Tompa, M. (2002) · Journal of Computational Biology · doi:10.1089/10665270252935430 · Cited by 532
Keogh, E., & Pazzani, M. J. (1998) · Cited by 496
Self-citationLin, J. (2002) · Cited by 460
Self-citationOn 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-citationDistance measures for effective clustering of ARIMA time-series
Kalpakis, K., Gada, D., & Puttagunta, V. (2002) · Proceedings 2001 IEEE International Conference on Data Mining · doi:10.1109/icdm.2001.989529 · Cited by 442
Locally adaptive dimensionality reduction for indexing large time series databases
Chakrabarti, K., Keogh, E., Mehrotra, S., & Pazzani, M. (2002) · ACM Transactions on Database Systems · doi:10.1145/568518.568520 · Cited by 407
Self-citationFinding surprising patterns in a time series database in linear time and space
Keogh, E., Lonardi, S., & Chiu, B. '.-C. (2002) · Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/775047.775128 · Cited by 404
Self-citationPattern Extraction for Time Series Classification
Geurts, P. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-44794-6_10 · Cited by 292
Agrawal, R., Psaila, G., Wimmers, E. L., & Zaït, M. (1995) · Cited by 251
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
Hancock: a language for extracting signatures from data streams
Cortes, C., Fisher, K., Pregibon, D., & Rogers, A. (2000) · Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/347090.347094 · Cited by 179
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
Adaptive dimension reduction for clustering high dimensional data
Ding, C., He, X., Hongyuan Zha, B., & Simon, H. D. (2003) · Proceedings · doi:10.1109/icdm.2002.1183897 · Cited by 164
Initialization of iterative refinement clustering algorithms
Fayyad, U. M., Reina, C., & Bradley, P. (1998) · Cited by 156
On the analysis of indexing schemes
Hellerstein, J. M., Koutsoupias, E., & Papadimitriou, C. H. (1997) · ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS) · doi:10.1145/263661.263688 · Cited by 146
Shahabi, C., Tian, X., & Zhao, W. (2002) · International Conference on Scientific and Statistical Database Management · doi:10.1109/ssdm.2000.869778 · Cited by 121
Adaptive query processing for time-series data
Huang, Y.-W., & Yu, P. S. (1999) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/312129.318357 · Cited by 105
An introduction to mathematical statistics and its applications
Larsen, R. J., & Marx, M. L. (2005) · University of Maribor digital library (University of Maribor) · Cited by 99
Using signature files for querying time-series data
André-Jönsson, H., & Badal, D. Z. (1997) · Lecture notes in computer science · doi:10.1007/3-540-63223-9_120 · Cited by 93
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-citationFinding recurrent sources in sequences
Gionis, A., & Mannila, H. (2003) · Research in Computational Molecular Biology · doi:10.1145/640075.640091 · Cited by 74
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-citationApplication of subspace methods to the identification of a winding process
Bastogne, T., Noura, H. N., Richard, A., & Hittinger, J.-M. (1997) · European Control Conference (ECC) · doi:10.23919/ecc.1997.7082426 · Cited by 24
Lonardi, S., & Apostolico, A. (2001) · Purdue e-Pubs (Purdue University System) · Cited by 21
Self-citation
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-citationGraph based anomaly detection and description: a survey
Akoglu, L., Tong, H., & Koutra, D. (2015) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-014-0365-y · Cited by 1,504
“We also include other discretization techniques that could apply under this setting such as SAX [Lin et al., 2003], MDL-binning [Kontkanen and Myllymki, 2007], and minimum entropy discretization [Fayyad and Irani, 1993].”
MethodA 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
Outlier Detection for Temporal Data: A Survey
Gupta, M., Gao, J., Aggarwal, C. C., & Han, J. (2014) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2013.184 · Cited by 1,001
Metadata
- Authors
- Lin, J., Keogh, E., Lonardi, S., & Chiu, B.
- Venue
- Proceedings of the 8th ACM SIGMOD workshop on Research issues in data mining and knowledge discovery
- Publisher
- ACM
- Published
- 2003-06-13
- Pages
- 2-11
- OpenAlex
- W1989037929
- Cited by
- 1,799
- References
- 37
- FWCI
- 27.56
- 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.