The DOI matches its Crossref record; 28 of the 28 references it cites were found in a registry or an index.
Similarity search over time-series data using wavelets
Abstract
Considers the use of wavelet transformations as a dimensionality reduction technique to permit efficient similarity searching over high-dimensional time-series data. While numerous transformations have been proposed and studied, the only wavelet that has been shown to be effective for this application is the Haar wavelet. In this work, we observe that a large class of wavelet transformations (not only orthonormal wavelets but also bi-orthonormal wavelets) can be used to support similarity searching. This class includes the most popular and most effective wavelets being used in image compression. We present a detailed performance study of the effects of using different wavelets on the performance of similarity searching for time-series data. We include several wavelets that outperform both the Haar wavelet and the best-known non-wavelet transformations for this application. To ensure our results are usable by an application engineer, we also show how to configure an indexing strategy for the best-performing transformations. Finally, we identify classes of data that can be indexed efficiently using these wavelet transformations.
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
Daubechies, I. (1992) · doi:10.1137/1.9781611970104 · Cited by 15,979
Daubechies, I., & Heil, C. (1992) · Computers in Physics · doi:10.1063/1.4823127 · Cited by 15,631
Introduction to Statistical Pattern Recognition
(1990) · Elsevier eBooks · doi:10.1016/c2009-0-27872-x · Cited by 11,031
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
Vetterli, M., & Kovačević, J. (1995) · Infoscience (Ecole Polytechnique Fédérale de Lausanne) · Cited by 2,898
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
M-tree: An Efficient Access Method for Similarity Search in Metric Spaces
Ciaccia, P., Patella, M., & Zezula, P. (1997) · Cited by 1,527
Berchtold, S., Keim, D. A., & Kriegel, H.-P. (2002) · Readings in Multimedia Computing and Networking · doi:10.1016/b978-155860651-7/50124-8 · Cited by 1,118
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
The SR-tree: an index structure for high-dimensional nearest neighbor queries
Katayama, N., & Satoh, S. (1997) · Proceedings of the 1997 ACM SIGMOD international conference on Management of data - SIGMOD '97 · doi:10.1145/253260.253347 · Cited by 817
Fractals, chaos, power laws: minutes from an infinite paradise
(1992) · Choice Reviews Online · doi:10.5860/choice.29-2770 · Cited by 811
Fast Time Sequence Indexing for Arbitrary Lp Norms
Yi, B.-K., & Faloutsos, C. (2018) · doi:10.1184/r1/6605618 · Cited by 650
Similarity 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
The X Tree: An Index Structure for High Dimensional Data
Berchtold, S., Keim, D. A., & Kriegel, H.-P. (1996) · KOPS (University of Konstanz) · Cited by 414
Content-based image indexing and searching using Daubechies' wavelets
Wang, J. Z., Wiederhold, G., Firschein, O., & Xin Wei, S. (1998) · International Journal on Digital Libraries · doi:10.1007/s007990050026 · Cited by 357
Similarity-based queries for time series data
Rafiei, D., & Mendelzon, A. O. (1997) · Proceedings - ACM-SIGMOD International Conference on Management of Data · doi:10.1145/253260.253264 · Cited by 340
WaveCluster: a wavelet-based clustering approach for spatial data in very large databases
Sheikholeslami, G., Chatterjee, S., & Zhang, A. (2000) · The VLDB Journal The International Journal on Very Large Data Bases · doi:10.1007/s007780050009 · Cited by 293
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
The Fastest Fourier Transform in the West
Frigo, M., & Johnson, S. G. (1997) · doi:10.21236/ada479065 · Cited by 244
The hybrid tree: an index structure for high dimensional feature spaces
Chakrabarti, K., & Mehrotra, S. (1999) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.1999.754960 · Cited by 207
The Haar Wavelet Transform in the Time Series Similarity Paradigm
Struzik, Z. R., & Siebes, A. P. J. M. (1999) · Lecture notes in computer science · doi:10.1007/978-3-540-48247-5_2 · Cited by 133
Wavelet-based image indexing techniques with partial sketch retrieval capability
Wang, J. Z., Wiederhold, G. C. M., Firschein, O., & Wei, S. X. (2002) · IEEE International Forum on Research and Technology Advances in Digital Libraries (ADL) · doi:10.1109/adl.1997.601196 · Cited by 133
Dimensionality reduction for similarity searching in dynamic databases
Kanth, K. V. R., Agrawal, D., & Singh, A. K. (1998) · ACM SIGMOD Record · doi:10.1145/276305.276320 · Cited by 123
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
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
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
Ezugwu, A. E., Ikotun, A. M., Oyelade, O. O., Abualigah, L., Agushaka, J. O., Eke, C. I., & Akinyelu, A. A. (2022) · Engineering Applications of Artificial Intelligence · doi:10.1016/j.engappai.2022.104743 · Cited by 924
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
Metadata
- Authors
- Popivanov, I., & Miller, R. J.
- Venue
- Proceedings 18th International Conference on Data Engineering
- Publisher
- IEEE Comput. Soc
- Published
- 2003-06-25
- Pages
- 212-221
- ISSN
- 1084-4627 (ISSN-L)
- OpenAlex
- W2138087993
- Cited by
- 280
- References
- 28
- FWCI
- 17.04
- 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.