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
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
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Locally adaptive dimensionality reduction for indexing large time series databases. https://app.cochat.ai/papers/10.1145/376284.375680
- The paper
- Keogh, E., Chakrabarti, K., Pazzani, M., & Mehrotra, S. (2001). Locally adaptive dimensionality reduction for indexing large time series databases. ACM SIGMOD Record. https://doi.org/10.1145/376284.375680
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.