Fast Similarity Search of Multi-dimensional Time Series via Segment Rotation

摘要

Multi-dimensional time series is playing an increasingly important role in the "big data" era, one noticeable representative being the pervasive trajectory data. Numerous applications of multi-dimensional time series all require to find similar time series of a given one, and regarding this purpose, Dynamic Time Warping (DTW) is the most widely used distance measure. Due to the high computation overhead of DTW, many lower bounding methods have been proposed to speed up similarity search. However, almost all the existing lower bounds are for general time series, which means they do not take advantage of the unique characteristics of higher dimensional time series. In this paper, we introduce a new lower bound for constrained DTW on multi-dimensional time series to achieve fast similarity search. The key observation is that when the time series is multi-dimensional, it can be rotated around the time axis, which helps to minimize the bounding envelope, thus improve the tightness, and in consequence the pruning power, of the lower bound. The experiment result on real world datasets demonstrates that our proposed method achieves faster similarity search than state-of-the-art techniques based on DTW.