An Indexable Time Series Dimensionality Reduction Method for Maximum Deviation Reduction and Similarity Search

Xue, Ruidong; Yu, Weiren; Wang, Hongxia

Abstract

Similarity search over time series is essential in many applications. However, it may cause “the curse of dimensionality” due to the high dimensionality of time series. Various dimensionality reduction methods have been developed. Some of them sacrifice maximum deviation to get faster dimensionality reduction. The Adaptive Piecewise Linear Approximation (APLA) method uses guaranteed error bounds for the best maximum deviation, but it takes a long time for dimensionality reduction. We propose an adaptive-length dimensionality reduction method, called Self Adaptive Piecewise Linear Approximation (SAPLA). It consists of 1) initialization; 2) split & merge iteration; and 3) segment end-point movement iteration. Increment Area, Reconstruction Area, and several equations are applied to prune redundant computations. Experiments show that our method outperforms APLA by n times with a minor maximum deviation loss, where n is the length of the time series. We also propose a lower bound distance measure between time series to guarantee lower bounding lemma and tightness for adaptive-length dimensionality reduction methods. Moreover, we propose a Distance-Based Covering with Convex Hull (DBCH ) structure to improve APCA MBR for adaptive-length dimensionality reduction methods. When mapping time series into a DBCH-tree, we split nodes and pick branches using the lower bounding distance. Our experimental evaluations on 117 datasets from the UCR2018 Archive demonstrate the efficiency and effectiveness of the proposed approaches.

Citation

Xue, R., Yu, W., & Wang, H. (2022, March). An Indexable Time Series Dimensionality Reduction Method for Maximum Deviation Reduction and Similarity Search. Presented at International Conference on Extending Database Technology (ACM EDBT'22)), Edinburgh, UK and online

• Presentation Conference Type: Conference Paper (published)
• Conference Name: International Conference on Extending Database Technology (ACM EDBT'22))
• Start Date: Mar 29, 2022
• End Date: Apr 1, 2022
• Acceptance Date: Mar 10, 2022
• Online Publication Date: Mar 23, 2022
• Publication Date: Mar 23, 2022
• Deposit Date: Jan 20, 2025
• Publicly Available Date: Jan 30, 2025
• Peer Reviewed: Peer Reviewed
• Pages: 183-195
• Series ISSN: 2367-2005
• Book Title: Proceedings of the 25th International Conference on Extending Database Technology (EDBT), 29th March-1st April, 2022
• ISBN: 9783893180857
• DOI: https://doi.org/10.48786/edbt.2022.08
• Keywords: Dimensionality Reduction, Data Mining, Time Series, kNN, Data Stream
• Public URL: https://nottingham-repository.worktribe.com/output/44421825
• Publisher URL: https://openproceedings.org/2022/conf/edbt/paper-41.pdf
• External URL: http://dx.doi.org/10.48786/edbt.2022.08