The DOI matches its Crossref record; 24 of the 24 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
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
Keogh, E., & Pazzani, M. J. (1998) · Cited by 496
Self-citationOptimal 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
Proceedings of the 31st international conference on Very large data bases
Bratbergsengen, K. (2005) · International Conference on Multimodal Interfaces · Cited by 414
Efficiently supporting ad hoc queries in large datasets of time sequences
Korn, F., Jagadish, H. V., & Faloutsos, C. (1997) · Proceedings of the 1997 ACM SIGMOD international conference on Management of data - SIGMOD '97 · doi:10.1145/253260.253332 · Cited by 405
Proceedings of the 3rd International Conference on Knowledge Discovery and Data Mining
Heckerman, D. E., Uthurusamy, R., Mannila, H., & Pregibon, D. (1997) · AAAI Press eBooks · Cited by 271
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 probabilistic approach to fast pattern matching in time series databases
Keogh, E., & Smyth, P. (1997) · Knowledge Discovery and Data Mining · Cited by 254
Self-citationA 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
An Eigenspace Update Algorithm for Image Analysis
Chandrasekaran, S., Manjunath, B. S., Wang, Y. F., Winkeler, J., & Zhang, H. (1997) · Graphical Models and Image Processing · doi:10.1006/gmip.1997.0425 · Cited by 233
Local Dimensionality Reduction: A New Approach to Indexing High Dimensional Spaces
Chakrabarti, K., & Mehrotra, S. (2000) · Cited by 230
Self-citationOn 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
Waveform Segmentation Through Functional Approximation
Pavlidis, T. (1973) · IEEE Transactions on Computers · doi:10.1109/tc.1973.5009136 · Cited by 136
Relevance feedback retrieval of time series data
Keogh, E., & Pazzani, M. J. (1999) · International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR) · doi:10.1145/312624.312676 · Cited by 109
Self-citationAdaptive 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
Supporting content-based searches on time series via approximation
Wang, C., & Wang, X. S. (2002) · International Conference on Scientific and Statistical Database Management · doi:10.1109/ssdm.2000.869779 · Cited by 99
Density-based indexing for approximate nearest-neighbor queries
Bennett, K. P., Fayyad, U. M., & Geiger, D. (1999) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/312129.312236 · Cited by 97
Fast retrieval of similar subsequences in long sequence databases
Park, S., Lee, D., & Chu, W. W. (2003) · doi:10.1109/kdex.1999.836610 · Cited by 86
Li, C., Yu, P. S., & Castelli, V. (1998) · ACM International Conference on Information and Knowledge Management (CIKM) · doi:10.1145/288627.288666 · Cited by 78
Supporting fast search in time series for movement patterns in multiple scales
Qu, Y., Wang, C., & Wang, X. S. (1998) · ACM International Conference on Information and Knowledge Management (CIKM) · doi:10.1145/288627.288664 · Cited by 76
Efficient retrieval for browsing large image databases
Wu, D. D., Singh, A. K., Agrawal, D., Abbadi, A. E., & Smith, T. R. (1996) · ACM International Conference on Information and Knowledge Management (CIKM) · doi:10.1145/238355.238365 · Cited by 71
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
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
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-citationRotation-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
Metadata
- Authors
- Keogh, E., Chakrabarti, K., Pazzani, M., & Mehrotra, S.
- Venue
- ACM SIGMOD Record
- Published
- 2001-05
- Volume
- 30
- Issue
- 2
- Pages
- 151-162
- ISSN
- 0163-5808 (ISSN-L)
- OpenAlex
- W3004804023
- Cited by
- 296
- References
- 24
- FWCI
- 5.95
- Type
- journal article
- 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.