一种基于动态时间弯曲距离的快速子序列匹配算法
2017-04-10刘晓影
刘晓影



摘 要: 动态时间弯曲距离在用于计算时间序列间的距离时是极其耗费时间的,尤其是处理较大规模的时间序列数据库中的子序列匹配问题时,时间消耗更是难以忍受。该文提出一种新的低边界距离,能够快速滤掉不满足结果条件的时间序列,以提高查询速度,并证明该低边界距离不会丢弃真实的结果。一种基于水平边界区域的索引技术被用于进一步提高查询效率。分别以真实数据集和人造数据集作为实验数据来测试该文所提出的算法的性能,结果表明该算法在数据库规模上和序列长度上都有良好的健壮性。
关键词: 时间弯曲距离; 低边界距离; 范围查询; 数据库
中图分类号: TN911?34; TP311.13 文献标识码: A 文章编号: 1004?373X(2017)06?0025?06
Abstract: 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 query 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.
Keywords: time warping distance; lower bounding distance; range query; database
0 引 言
时间序列是由一些在特定时间点上采样得到的实数组成。在现实世界中,有很多时间序列的例子,如股票的价格、天气的变化情况、商品的销售记录。时间序列间的相似性查询就是从时间序列数据库中发现与给定查询序列有相似的变化模式的序列,该操作在很多新的数据库应用领域(数据挖掘、数据仓库)中是很重要的,它能用于预测未来发展趋势、识别新的模式、发现规则[1?3]。例如,可能需要找出一天的股票价格中的特定模式来预测未来发展趋势;也可能需要找出历史上与今天有相似磁暴模式的日子来预测地球磁场的变化。
通常,时间序列相似性查询可以分为两类:全序列匹配和子序列匹配。全序列匹配是给定一条查询序列,在数据库中找出与其相似的完整数据序列,而子序列匹配是在数据库中找出与其相似的部分数据序列,即子序列。……
