一种基于动态时间弯曲距离的快速子序列匹配算法

Fast subsequence matching algorithm based on dynamic time warping distance

动态时间弯曲距离在用于计算时间序列间的距离时是极其耗费时间的,尤其是处理较大规模的时间序列数据库中的子序列匹配问题时,时间消耗更是难以忍受。该文提出一种新的低边界距离,能够快速滤掉不满足结果条件的时间序列,以提高查询速度,并证明该低边界距离不会丢弃真实的结果。一种基于水平边界区域的索引技术被用于进一步提高查询效率。分别以真实数据集和人造数据集作为实验数据来测试该文所提出的算法的性能,结果表明该算法在数据库规模上和序列长度上都有良好的健壮性。

It is very time?consuming to calculate the distance between time sequences by using dynamic time warping distance,especially when the subsequence matching in large time?series databases is concerned.A new method of lower bound distance is presented in this paper,which can quickly filter the time sequences which are unable to satisfy the result condition,so as to improve the query speed.It is proven that the true results can not be lost if the method is used.To further increase the que?ry speed,a technique for building an index based on skyline bounding region is also proposed.Some experiments with the data from real data set and synthetic data set were carried out to verify the performance of the methods.The results reveal that the method has robostness in the scale of database and sequence length.