一种支持DTW距离的多元时间序列索引结构

Index Structure for Multivariate Time Series under DTW Distance Metric

现有的索引结构难以有效地支持DTW距离度量下的多元时间序列相似性搜索.首先给出一种将不等长多元时间序列转换为等长一元时间序列的方法,并证明这种转换满足下界距离引理;以此为基础,提出一种多元时间序列的DTW下界距离,并对其性质进行分析;然后,针对给出的下界距离,提出一种支持DTW距离度量的多元时间序列索引结构,对多元时间序列数据库进行有效组织;再给出多元时间序列相似模式搜索算法及流程,并证明该搜索方法具有非漏报性;最后,通过实验对所提方法的有效性进行验证.

Existing index structures for multivariate time series can＇t support similarity search under DTW distance efficiently. Firstly, a transformation method, which converts unequal-length multivariate time series into equal-length univariate time series, is proposed and a mathematical proof that the transformation satisfies lower bounding distance lemma is provided. Secondly, DTW lower bounding distance is proposed, and its character is analyzed. Thirdly, based on DTW lower bounding distance proposed above, an index structure for multivariate time series is proposed, allowing database of multivariate time series be organized. Further, similarity search algorithm and process for multivariate time series are discussed, and related mathematical proofs that false dismissals can be avoided are given. Finally, validity of proposed method is verified by experiments.