The Library
An indexable time series dimensionality reduction method for maximum deviation reduction and similarity search
Tools
Xue, Ruidong, Yu, Weiren and Wang, Hongxia (2022) An indexable time series dimensionality reduction method for maximum deviation reduction and similarity search. In: Extending Database Technology (ACM EDBT’22), Edinburgh, UK, 29 Mar - 01 Apr 2022. Published in: Proceedings of the 25th International Conference on Extending Database Technology (ACM EDBT’22), 25 (2). pp. 183-195. ISBN 9783893180857. doi:10.48786/edbt.2022.08 ISSN 2367-2005.
|
PDF
WRAP-An-indexable-time-series-dimensionality-reduction-method-Yu-2022.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution Non-commercial No Derivatives 4.0. Download (1316Kb) | Preview |
Official URL: http://dx.doi.org/10.48786/edbt.2022.08
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.
Item Type: | Conference Item (Paper) | |||||||||
---|---|---|---|---|---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | |||||||||
Journal or Publication Title: | Proceedings of the 25th International Conference on Extending Database Technology (ACM EDBT’22) | |||||||||
Publisher: | Open Proceedings | |||||||||
ISBN: | 9783893180857 | |||||||||
ISSN: | 2367-2005 | |||||||||
Official Date: | 23 March 2022 | |||||||||
Dates: |
|
|||||||||
Volume: | 25 | |||||||||
Number: | 2 | |||||||||
Page Range: | pp. 183-195 | |||||||||
DOI: | 10.48786/edbt.2022.08 | |||||||||
Status: | Peer Reviewed | |||||||||
Publication Status: | Published | |||||||||
Access rights to Published version: | Open Access (Creative Commons) | |||||||||
Date of first compliant deposit: | 29 March 2022 | |||||||||
Date of first compliant Open Access: | 13 April 2022 | |||||||||
RIOXX Funder/Project Grant: |
|
|||||||||
Conference Paper Type: | Paper | |||||||||
Title of Event: | Extending Database Technology (ACM EDBT’22) | |||||||||
Type of Event: | Conference | |||||||||
Location of Event: | Edinburgh, UK | |||||||||
Date(s) of Event: | 29 Mar - 01 Apr 2022 | |||||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year