一种基于动态时间弯曲的数据流子序列匹配系统

A Subsequence Matching System Over Data Stream Under Dynamic Time Warping

随着工业生产中数据源的不断增加,人们对数据流的处理需求日益增大.其中,一个基本需求是基于距离度量方法的子序列匹配.由于动态时间弯曲距离(dynamic time warping,DTW)具有较高的度量精度,将其应用于子序列匹配问题是非常有价值的.但是,DTW具有较高的计算复杂度,这极大地限制了它在数据流上的应用.针对该问题,设计了一种高效的基于DTW的数据流子序列匹配系统.首先对数据流进行高效的适应性分段,然后对每一子段进行切比雪夫因式分解.不同于在原始数据空间的DTW计算,系统将在低维的切比雪夫特征空间计算DTW距离,因此,系统具有较高的计算效率.另外,提出了一种高效的在线匹配算法,可实现DTW在数据流上的增量式计算,进一步提高了系统的执行效率.

With the increment of data sources,there are many challenging demands to deal with the data stream.The most fundamental one is the subsequence matching based on the distance measures.With the high measure precision,the dynamic time warping(DTW)distance has been proven valuable to be used for the subsequence matching.Unfortunately,the high computational complexity of DTW largely limits its application to the data stream.To address this problem,we propose a novel piecewise approximation based DTW and design an efficient subsequence matching system over data stream under DTW.Concretely,we first adaptively segment the data stream,and then factorize each segment with the Chebyshev polynomials.Rather than on the raw data,DTW is computed in the lowdimensional Chebyshev space. Moreover,we propose an efficient online matching algorithm to support the incremental DTW computation over data stream,which can further improve the efficiency of the system.