The DOI matches its Crossref record; 17 of the 17 references it cites were found in a registry or an index.
Fast subsequence matching in time-series databases
Abstract
We present an efficient indexing method to locate 1-dimensional subsequences within a collection of sequences, such that the subsequences match a given (query) pattern within a specified tolerance. The idea is to map each data sequences into a small set of multidimensional rectangles in feature space. Then, these rectangles can be readily indexed using traditional spatial access methods, like the R*-tree [9]. In more detail, we use a sliding window over the data sequence and extract its features; the result is a trail in feature space. We propose an efficient and effective algorithm to divide such trails into sub-trails, which are subsequently represented by their Minimum Bounding Rectangles (MBRs). We also examine queries of varying lengths, and we show how to handle each case efficiently. We implemented our method and carried out experiments on synthetic and real data (stock price movements). We compared the method to sequential scanning, which is the only obvious competitor. The results were excellent: our method accelerated the search time from 3 times up to 100 times.
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
Basic local alignment search tool
Altschul, S. F., Gish, W., Miller, W., Myers, E. W., & Lipman, D. J. (1990) · Journal of Molecular Biology · doi:10.1006/jmbi.1990.9999 · Cited by 98,669
The Fractal Geometry of Nature
Mandelbrot, B. B., & Wheeler, J. A. (1983) · American Journal of Physics · doi:10.1119/1.13295 · Cited by 21,832
Mining association rules between sets of items in large databases
Agrawal, R., Imieliński, T., & Swami, A. (1993) · Proceedings of the 1993 ACM SIGMOD international conference on Management of data · doi:10.1145/170035.170072 · Cited by 14,907
R-trees: a dynamic index structure for spatial searching
Guttman, A. (1984) · Proceedings of the 1984 ACM SIGMOD international conference on Management of data - SIGMOD '84 · doi:10.1145/602259.602266 · Cited by 6,580
The R*-tree: an efficient and robust access method for points and rectangles
Beckmann, N., Kriegel, H.-P., Schneider, R., & Seeger, B. (1990) · Proceedings of the 1990 ACM SIGMOD international conference on Management of data · doi:10.1145/93597.98741 · Cited by 4,161
The JPEG still picture compression standard
Wallace, G. K. (1991) · Communications of the ACM · doi:10.1145/103085.103089 · Cited by 3,784
The Analysis of Time Series: An Introduction
Dickey, D. A., & Chatfield, C. (1991) · Technometrics · doi:10.2307/1268794 · Cited by 3,525
The design and analysis of spatial data structures
Samet, H. (1989) · CERN Document Server (European Organization for Nuclear Research) · Cited by 2,380
Efficient similarity search in sequence databases
Agrawal, R., Faloutsos, C., & Swami, A. (1993) · Lecture Notes in Computer Science · doi:10.1007/3-540-57301-1_5 · Cited by 1,979
Self-citationQBIC project: querying images by content, using color, texture, and shape:
Niblack, C. W., Barber, R., Equitz, W., Flickner, M. D., Glasman, E. H., Petkovic, D., Yanker, P., Faloutsos, C., & Taubin, G. (1993) · SPIE Proceedings · doi:10.1117/12.143648 · Cited by 1,747
Self-citation
Cited by
Data mining: concepts and techniques
(2012) · Choice Reviews Online · doi:10.5860/choice.49-3305 · Cited by 28,531
A Survey of Clustering Data Mining Techniques
Berkhin, P. (2006) · Grouping Multidimensional Data · doi:10.1007/3-540-28349-8_2 · Cited by 2,804
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
Data mining: an overview from a database perspective
Chen, M.-S., Han, J., & Yu, P. S. (1996) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/69.553155 · Cited by 2,232
Exact indexing of dynamic time warping
Keogh, E., & Ratanamahatana, C. A. (2005) · Knowledge and Information Systems · doi:10.1007/s10115-004-0154-9 · Cited by 1,962
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
A symbolic representation of time series, with implications for streaming algorithms
Lin, J., Keogh, E., Lonardi, S., & Chiu, B. (2003) · Proceedings of the 8th ACM SIGMOD workshop on Research issues in data mining and knowledge discovery · doi:10.1145/882082.882086 · Cited by 1,799
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
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
A 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
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
Ding, H., Trajcevski, G., Scheuermann, P., Wang, X., & Keogh, E. (2008) · Proceedings of the VLDB Endowment · doi:10.14778/1454159.1454226 · Cited by 1,354
Hand, D. J. (2007) · Drug Safety · doi:10.2165/00002018-200730070-00010 · Cited by 1,044
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
Esling, P., & Agon, C. (2012) · ACM Computing Surveys · doi:10.1145/2379776.2379788 · Cited by 997
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
On 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
Experimental comparison of representation methods and distance measures for time series data
Wang, X., Mueen, A., Ding, H., Trajcevski, G., Scheuermann, P., & Keogh, E. (2013) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-012-0250-5 · Cited by 845
Böhm, C., Berchtold, S., & Keim, D. A. (2001) · ACM Computing Surveys · doi:10.1145/502807.502809 · Cited by 827
Scaling up dynamic time warping for datamining applications
Keogh, E. J., & Pazzani, M. J. (2000) · Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/347090.347153 · Cited by 820
Map-matching for low-sampling-rate GPS trajectories
Lou, Y., Zhang, C., Zheng, Y., Xie, X., Wang, W., & Huang, Y. (2009) · Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems · doi:10.1145/1653771.1653820 · Cited by 797
On The Marriage of Lp-norms and Edit Distance
Chen, L., & Ng, R. (2004) · Proceedings 2004 VLDB Conference · doi:10.1016/b978-012088469-8.50070-x · Cited by 774
k-Shape: Efficient and Accurate Clustering of Time Series
Paparrizos, J., & Gravano, L. (2015) · Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data · doi:10.1145/2723372.2737793 · Cited by 680
Characteristic-Based Clustering for Time Series Data
Wang, X., Smith, K., & Hyndman, R. (2006) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-005-0039-x · Cited by 679
Zhu, Y., & Shasha, D. (2002) · VLDB '02: Proceedings of the 28th International Conference on Very Large Databases · doi:10.1016/b978-155860869-6/50039-1 · Cited by 656
Fast Time Sequence Indexing for Arbitrary Lp Norms
Yi, B.-K., & Faloutsos, C. (2018) · doi:10.1184/r1/6605618 · Cited by 650
Self-citationSimilarity indexing with the SS-tree
White, D. A., & Jain, R. (2002) · Proceedings of the Twelfth International Conference on Data Engineering · doi:10.1109/icde.1996.492202 · Cited by 635
Overview of multidatabase transaction management
Breitbart, Y., Garcia-Molina, H., & Silberschatz, A. (1992) · The VLDB Journal · doi:10.1007/bf01231700 · Cited by 565
Exact Indexing of Dynamic Time Warping
Keogh, E. (2002) · VLDB '02: Proceedings of the 28th International Conference on Very Large Databases · doi:10.1016/b978-155860869-6/50043-3 · Cited by 532
Automated extraction and parameterization of motions in large data sets
Kovar, L., & Gleicher, M. (2004) · ACM Transactions on Graphics · doi:10.1145/1015706.1015760 · Cited by 483
Multi-Scale Convolutional Neural Networks for Time Series Classification
Cui, Z., Chen, W., & Chen, Y. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1603.06995 · Cited by 455
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
Distance 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
Optimal multi-step k-nearest neighbor search
Seidl, T., & Kriegel, H.-P. (1998) · Proceedings of the 1998 ACM SIGMOD international conference on Management of data · doi:10.1145/276304.276319 · Cited by 442
Lubba, C. H., Sethi, S. S., Knaute, P., Schultz, S. R., Fulcher, B. D., & Jones, N. S. (2019) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-019-00647-x · Cited by 431
Time series shapelets: a novel technique that allows accurate, interpretable and fast classification
Ye, L., & Keogh, E. (2011) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-010-0179-5 · Cited by 406
“…(Faloutsos et al. 1994) and Symbolic Aggregate approXimation (SAX) (Lin et al. 2007), and different similarity measures, such as Euclidean Distance (Faloutsos et al. 1994) and Dynamic Time Warping (DTW) (Berndt and Clifford 1994; Keogh and Ratanamahatana 2005), a recent large scale set of…”
BackgroundMethodInfluentialMaking Time-series Classification More Accurate Using Learned Constraints
Ratanamahatana, C. A., & Keogh, E. (2004) · Proceedings of the 2004 SIAM International Conference on Data Mining · doi:10.1137/1.9781611972740.2 · Cited by 407
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
Finding 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
A survey of temporal knowledge discovery paradigms and methods
Roddick, J. F., & Spiliopoulou, M. (2002) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2002.1019212 · Cited by 397
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
Using dynamic time warping distances as features for improved time series classification
Kate, R. J. (2016) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-015-0418-x · Cited by 348
Distance-based indexing for high-dimensional metric spaces
Bozkaya, T., & Ozsoyoglu, M. (1997) · Proceedings of the 1997 ACM SIGMOD international conference on Management of data - SIGMOD '97 · doi:10.1145/253260.253345 · Cited by 332
A Complexity-Invariant Distance Measure for Time Series
Batista, G. E. A. P. A., Wang, X., & Keogh, E. J. (2011) · Proceedings of the 2011 SIAM International Conference on Data Mining · doi:10.1137/1.9781611972818.60 · Cited by 329
i SAX: indexing and mining terabyte sized time series
Shieh, J., & Keogh, E. (2008) · Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1401890.1401966 · Cited by 323
Indexing spatio-temporal trajectories with Chebyshev polynomials
Cai, Y., & Ng, R. (2004) · Proceedings of the 2004 ACM SIGMOD international conference on Management of data · doi:10.1145/1007568.1007636 · Cited by 309
Rise and fall patterns of information diffusion: model and implications
Matsubara, Y., Sakurai, Y., Prakash, B. A., Li, L., & Faloutsos, C. (2012) · Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/2339530.2339537 · Cited by 306
Self-citationReal-time classification of dance gestures from skeleton animation
Raptis, M., Kirovski, D., & Hoppe, H. (2011) · Proceedings of the 2011 ACM SIGGRAPH/Eurographics Symposium on Computer Animation · doi:10.1145/2019406.2019426 · Cited by 302
Landmarks: a new model for similarity-based pattern querying in time series databases
Perng, C.-S., Wang, H., Zhang, S. R., & Parker, D. S. (2002) · Proceedings of 16th International Conference on Data Engineering (Cat. No.00CB37073) · doi:10.1109/icde.2000.839385 · Cited by 297
Locally adaptive dimensionality reduction for indexing large time series databases
Keogh, E., Chakrabarti, K., Pazzani, M., & Mehrotra, S. (2001) · ACM SIGMOD Record · doi:10.1145/376284.375680 · Cited by 296
Rotation-invariant similarity in time series using bag-of-patterns representation
Lin, J., Khade, R., & Li, Y. (2012) · Journal of Intelligent Information Systems · doi:10.1007/s10844-012-0196-5 · Cited by 295
Similarity search over time-series data using wavelets
Popivanov, I., & Miller, R. J. (2003) · Proceedings 18th International Conference on Data Engineering · doi:10.1109/icde.2002.994711 · Cited by 280
Iterative Deepening Dynamic Time Warping for Time Series
Chu, S., Keogh, E., Hart, D., & Pazzani, M. (2002) · Proceedings of the 2002 SIAM International Conference on Data Mining · doi:10.1137/1.9781611972726.12 · Cited by 268
Haar wavelets for efficient similarity search of time-series: with and without time warping
Chan, F. K., Fu, A. W.-C., & Yu, C. (2003) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2003.1198399 · Cited by 261
Dimensionality reduction for similarity searching in dynamic databases
Ravi Kanth, K. V., Agrawal, D., & Singh, A. (1998) · Proceedings of the 1998 ACM SIGMOD international conference on Management of data · doi:10.1145/276304.276320 · Cited by 256
A comparison of DFT and DWT based similarity search in time-series databases
Wu, Y.-L., Agrawal, D., & El Abbadi, A. (2000) · Proceedings of the ninth international conference on Information and knowledge management · doi:10.1145/354756.354857 · Cited by 253
Discrete Wavelet transform-based time series analysis and mining
Chaovalit, P., Gangopadhyay, A., Karabatis, G., & Chen, Z. (2011) · ACM Computing Surveys · doi:10.1145/1883612.1883613 · Cited by 218
Deep Unsupervised Binary Coding Networks for Multivariate Time Series Retrieval
Zhu, D., Song, D., Chen, Y., Lumezanu, C., Cheng, W., Zong, B., Ni, J., Mizoguchi, T., Yang, T., & Chen, H. (2020) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v34i02.5497 · Cited by 20
Metadata
- Authors
- Faloutsos, C., Ranganathan, M., & Manolopoulos, Y.
- Venue
- Proceedings of the 1994 ACM SIGMOD international conference on Management of data
- Publisher
- ACM
- Published
- 1994-05-24
- Pages
- 419-429
- ISSN
- 0730-8078 (ISSN-L)
- OpenAlex
- W2128061541
- Cited by
- 1,709
- References
- 17
- FWCI
- 37.83
- 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.