The DOI matches its Crossref record; 38 of the 38 references it cites were found in a registry or an index.
Locally adaptive dimensionality reduction for indexing large time series databases
Abstract
Similarity search in large time series databases has attracted much research interest recently. It is a difficult problem because of the typically high dimensionality of the data.. The most promising solutions involve performing dimensionality reduction on the data, then indexing the reduced data with a multidimensional index structure. Many dimensionality reduction techniques have been proposed, including Singular Value Decomposition (SVD), the Discrete Fourier transform (DFT), and the Discrete Wavelet Transform (DWT). In this work we introduce a new dimensionality reduction technique which we call Adaptive Piecewise Constant Approximation (APCA). While previous techniques (e.g., SVD, DFT and DWT) choose a common representation for all the items in the database that minimizes the global reconstruction error, APCA approximates each time series by a set of constant value segments of varying lengths such that their individual reconstruction errors are minimal. We show how APCA can be indexed using a multidimensional index structure. We propose two distance measures in the indexed space that exploit the high fidelity of APCA for fast searching: a lower bounding Euclidean distance approximation, and a non-lower bounding, but very tight Euclidean distance approximation and show how they can support fast exact searching, and even faster approximate searching on the same index structure. We theoretically and empirically compare APCA to all the other techniques and demonstrate its superiority.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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
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
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
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
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-citationRoussopoulos, N., Kelley, S., & Vincent, F. (1995) · Proceedings of the 1995 ACM SIGMOD international conference on Management of data - SIGMOD '95 · doi:10.1145/223784.223794 · Cited by 1,402
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
Wavelets for computer graphics: a primer.1
Stollnitz, E. J., DeRose, A. D., & Salesin, D. H. (1995) · IEEE Computer Graphics and Applications · doi:10.1109/38.376616 · Cited by 727
Wavelets for computer graphics: theory and applications
Stollnitz, E. J., DeRose, T., & Salesin, D. (1996) · Morgan Kaufmann Publishers Inc. eBooks · Cited by 696
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
Cited by
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
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
Self-citationTime-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
Self-citationExperiencing 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
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
Self-citationRobust and fast similarity search for moving object trajectories
Chen, L., Özsu, M. T., & Oria, V. (2005) · Proceedings of the 2005 ACM SIGMOD international conference on Management of data · doi:10.1145/1066157.1066213 · Cited by 1,336
Esling, P., & Agon, C. (2012) · ACM Computing Surveys · doi:10.1145/2379776.2379788 · Cited by 997
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
Self-citationExperimental 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
Self-citationOn 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
An Entropy Weighting k-Means Algorithm for Subspace Clustering of High-Dimensional Sparse Data
Jing, L., Ng, M. K., & Huang, J. Z. (2007) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2007.1048 · Cited by 625
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
Self-citationAutomated 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
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-citationMaking 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
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-citationThree Myths about Dynamic Time Warping Data Mining
Ratanamahatana, C. A., & Keogh, E. (2005) · Proceedings of the 2005 SIAM International Conference on Data Mining · doi:10.1137/1.9781611972757.50 · Cited by 393
Self-citationHighly Comparative Feature-Based Time-Series Classification
Fulcher, B. D., & Jones, N. S. (2014) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2014.2316504 · Cited by 343
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
Self-citationExposure: A Passive DNS Analysis Service to Detect and Report Malicious Domains
Bilge, L., Sen, S., Balzarotti, D., Kirda, E., & Kruegel, C. (2014) · ACM Transactions on Information and System Security · doi:10.1145/2584679 · Cited by 317
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
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
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
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
Identifying similarities, periodicities and bursts for online search queries
Vlachos, M., Meek, C., Vagena, Z., & Gunopulos, D. (2004) · Proceedings of the 2004 ACM SIGMOD international conference on Management of data · doi:10.1145/1007568.1007586 · Cited by 277
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
Mehdiyev, N., & Fettke, P. (2021) · Studies in Computational Intelligence · doi:10.1007/978-3-030-64949-4_1 · Cited by 78
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
- Keogh, E., Chakrabarti, K., Pazzani, M., & Mehrotra, S.
- Venue
- Proceedings of the 2001 ACM SIGMOD international conference on Management of data
- Publisher
- ACM
- Published
- 2001-05
- Pages
- 151-162
- ISSN
- 0730-8078 (ISSN-L)
- OpenAlex
- W2163336863
- Cited by
- 866
- References
- 38
- FWCI
- 37.01
- 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.