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-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
Esling, P., & Agon, C. (2012) · ACM Computing Surveys · doi:10.1145/2379776.2379788 · Cited by 997
(2015) · Cited by 989
Patterns of temporal variation in online media
Yang, J., & Leskovec, J. (2011) · Proceedings of the fourth ACM international conference on Web search and data mining · doi:10.1145/1935826.1935863 · Cited by 986
k-Nearest Neighbour Classifiers - A Tutorial
Cunningham, P., & Delany, S. J. (2022) · ACM Computing Surveys · doi:10.1145/3459665 · Cited by 942
Gaber, M. M., Zaslavsky, A., & Krishnaswamy, S. (2005) · ACM SIGMOD Record · doi:10.1145/1083784.1083789 · Cited by 886
Social big data: recent achievements and new challenges
Bello-Orgaz, G., Jung, J. J., & Camacho, D. (2016) · Information Fusion · doi:10.1016/j.inffus.2015.08.005 · Cited by 846
“[84] , a new symbolic representation of time series is proposed that allows for a dimensionality/numerosity reduction.”
BackgroundHOT SAX: Efficiently Finding the Most Unusual Time Series Subsequence
Keogh, E., Lin, J., & Fu, A. (2006) · Fifth IEEE International Conference on Data Mining (ICDM'05) · doi:10.1109/icdm.2005.79 · Cited by 696
Self-citationPreprocessing techniques for context recognition from accelerometer data
Figo, D., Diniz, P. C., Ferreira, D. R., & Cardoso, J. M. P. (2010) · Personal and Ubiquitous Computing · doi:10.1007/s00779-010-0293-9 · Cited by 578
“A recently developed techniques called symbolic aggregate approximation (SAX) uses a piecewise aggregate approximation (PAA) [31] which relies on a gaussian equiprobable distribution function to map range values into string symbols.”
BackgroundMethodInfluentialTowards parameter-free data mining
Keogh, E., Lonardi, S., & Ratanamahatana, C. A. (2004) · Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1014052.1014077 · Cited by 567
Self-citationDeep Learning for Sensor-based Human Activity Recognition
Chen, K., Zhang, D., Yao, L., Guo, B., Yu, Z., & Liu, Y. (2022) · ACM Computing Surveys · doi:10.1145/3447744 · Cited by 690
“ing methods in human activity recognition [79]. They highly rely on feature extraction techniques including time-frequency transformation [62], statistical approaches [21] and symbolic representation [88]. However, the features extracted are carefully engineered and heuristic. There were no universal or systematical f…”
Evaluating Real-Time Anomaly Detection Algorithms -- The Numenta Anomaly Benchmark
Lavin, A., & Ahmad, S. (2015) · 2015 IEEE 14th International Conference on Machine Learning and Applications (ICMLA) · doi:10.1109/icmla.2015.141 · Cited by 457
A deep learning approach to on-node sensor data analytics for mobile or wearable devices
Ravi, D., Wong, C., Lo, B., & Yang, G.-Z. (2017) · IEEE Journal of Biomedical and Health Informatics · doi:10.1109/jbhi.2016.2633287 · Cited by 439
TSclust: An R Package for Time Series Clustering
Montero, P., & Vilar, J. A. (2014) · Journal of Statistical Software · doi:10.18637/jss.v062.i01 · Cited by 430
Kasten, E. P., Gage, S. H., Fox, J., & Joo, W. (2012) · Ecological Informatics · doi:10.1016/j.ecoinf.2012.08.001 · Cited by 408
CID: an efficient complexity-invariant distance for time series
Batista, G. E. A. P. A., Keogh, E. J., Tataw, O. M., & de Souza, V. M. A. (2014) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-013-0312-3 · Cited by 359
Self-citationLSTM-Based EEG Classification in Motor Imagery Tasks
Wang, P., Jiang, A., Liu, X., Shang, J., & Zhang, L. (2018) · IEEE Transactions on Neural Systems and Rehabilitation Engineering · doi:10.1109/tnsre.2018.2876129 · Cited by 358
Clustering of Electricity Consumption Behavior Dynamics Toward Big Data Applications
Wang, Y., Chen, Q., Kang, C., & Xia, Q. (2016) · IEEE Transactions on Smart Grid · doi:10.1109/tsg.2016.2548565 · Cited by 342
Deep Learning for Sensor-based Human Activity Recognition: Overview, Challenges and Opportunities
Chen, K., Zhang, D., Yao, L., Guo, B., Yu, Z., & Liu, Y. (2020) · arXiv · doi:10.48550/arxiv.2001.07416 · Cited by 314
“ing methods in human activity recognition [79]. They highly rely on feature extraction techniques including time-frequency transformation [62], statistical approaches [21] and symbolic representation [88]. However, the features extracted are carefully engineered and heuristic. There were no universal or systematical f…”
Sequential pattern mining -- approaches and algorithms
Mooney, C. H., & Roddick, J. F. (2013) · ACM Computing Surveys · doi:10.1145/2431211.2431218 · Cited by 310
Gorilla: a fast, scalable, in-memory time series database
Pelkonen, T., Franklin, S., Teller, J., Cavallaro, P., Huang, Q., Meza, J., & Veeraraghavan, K. (2015) · Proceedings of the VLDB Endowment · doi:10.14778/2824032.2824078 · Cited by 290
Visual Methods for Analyzing Time-Oriented Data
Aigner, W., Miksch, S., Muller, W., Schumann, H., & Tominski, C. (2008) · IEEE Transactions on Visualization and Computer Graphics · doi:10.1109/tvcg.2007.70415 · Cited by 284
shapeDTW: Shape Dynamic Time Warping
Zhao, J., & Itti, L. (2018) · Pattern Recognition · doi:10.1016/j.patcog.2017.09.020 · Cited by 281
Ravi, D., Wong, C., Lo, B., & Yang, G.-Z. (2016) · 2016 IEEE 13th International Conference on Wearable and Implantable Body Sensor Networks (BSN) · doi:10.1109/bsn.2016.7516235 · Cited by 269
“Features, such as mean [1], Fourier transforms [2], and symbols [3], are typically extracted from segments of data and then trained using classification methods [4]–[8].”
BackgroundMethodLoad profiling and its application to demand response: A review
Wang, Y., Chen, Q., Kang, C., Zhang, M., Wang, K., & Zhao, Y. (2015) · Tsinghua Science and Technology · doi:10.1109/tst.2015.7085625 · Cited by 268
Explainable AI for clinical and remote health applications: A survey on tabular and time series data
Di Martino, F., & Delmastro, F. (2023) · Artificial Intelligence Review · doi:10.1007/s10462-022-10304-3 · Cited by 216
Temporal abstraction in intelligent clinical data analysis: A survey
Stacey, M., & McGregor, C. (2007) · Artificial Intelligence in Medicine · doi:10.1016/j.artmed.2006.08.002 · Cited by 146
Discovering Characteristic Actions from On-Body Sensor Data
Minnen, D., Starner, T., Essa, I., & Isbell, C. (2006) · 2006 10th IEEE International Symposium on Wearable Computers · doi:10.1109/iswc.2006.286337 · Cited by 132
Explainable Artificial Intelligence (XAI) on TimeSeries Data: A Survey
Rojat, T., Puget, R., Filliat, D., Del Ser, J., Gelin, R., & Díaz-Rodríguez, N. (2021) · arXiv · doi:10.48550/arxiv.2104.00950 · Cited by 116
Physical Activity Recognition from Accelerometer Data Using a Multi-Scale Ensemble Method
Zheng, Y., Won, W.-K., Guan, X., & Trost, S. (2013) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v27i2.18997 · Cited by 84
Classification of Heart Diseases Based On ECG Signals Using Long Short-Term Memory
Liu, M., & Kim, Y. (2018) · 2018 40th Annual International Conference of the IEEE Engineering in Medicine and Biology Society (EMBC) · doi:10.1109/embc.2018.8512761 · Cited by 83
Shi, Y., Du, J., & Worthy, D. A. (2020) · Automation in Construction · doi:10.1016/j.autcon.2020.103367 · Cited by 82
Censored Planet: An Internet-wide, Longitudinal Censorship Observatory
Sundara Raman, R., Shenoy, P., Kohls, K., & Ensafi, R. (2020) · Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/3372297.3417883 · Cited by 75
Fekr, A. R., Radecka, K., & Zilic, Z. (2015) · IEEE Journal of Biomedical and Health Informatics · doi:10.1109/jbhi.2015.2445783 · Cited by 61
“[53] introduced the SAX which allows a time series C of length n to be represented in a w-dimensional space by a vector C = c1 , .”
BackgroundMethodInfluentialMorid, M. A., Sheng, O. R. L., Kawamoto, K., & Abdelrahman, S. (2020) · Journal of Biomedical Informatics · doi:10.1016/j.jbi.2020.103565 · Cited by 49
Modeling the neurodynamic organizations and interactions of teams
Stevens, R. H., & Galloway, T. L. (2016) · Social Neuroscience · doi:10.1080/17470919.2015.1056883 · Cited by 29
A Framework for Automatic Text Generation of Trends in Physiological Time Series Data
Banaee, H., Ahmed, M. U., & Loutfi, A. (2013) · 2013 IEEE International Conference on Systems, Man, and Cybernetics · doi:10.1109/smc.2013.661 · Cited by 21
“[8] to represent the main obvious attributes of the signals.”
BackgroundOwadally, I., Zhou, F., Otunba, R., Lin, J., & Wright, D. (2019) · Expert Systems with Applications · doi:10.1016/j.eswa.2019.01.049 · Cited by 16
Self-citationKumar, P., & Chauhan, S. (2021) · CCF Transactions on Pervasive Computing and Interaction · doi:10.1007/s42486-021-00063-5 · Cited by 13
RetractedJangir, M. K., & Singh, K. (2019) · Journal of Discrete Mathematical Sciences and Cryptography · doi:10.1080/09720529.2019.1696552 · Cited by 11
“In some applications, to describe the time series data, we have a set of shallow features viz. statistical parameters [6], basis transform coding [7], and symbolic representation [8].”
BackgroundOrdonez, P., Armstrong, T., Oates, T., & Fackler, J. (2011) · 2011 10th International Conference on Machine Learning and Applications and Workshops · doi:10.1109/icmla.2011.46 · Cited by 8
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.