Fast subsequence matching under time warping in time-series databases

This paper investigates the problem of subsequence matching under time warping in large time-series databases. We introduce a lower bound distance for subsequence matching, which is proven to incur no false dismissals. We also propose two novel methods to construct indexes for subsequence matching: SubRFM and SubSBR. Compared to recent methods, the advantage of our methods is that they can find all the fruitful results without length limitation. To verify the performance of our methods, we carried out experiments on real world data and large synthetic data. The results reveal that the two methods achieve significant speedup compared to sequential search.