时序数据库中快速相似搜索的算法研究

RESEARCH ON FAST RETRIEVAL OF SIMILARITY PATTERNS IN A TIME SERIES DATABASE

针对时间序列,本文提出了一种新的数据表示方法。该方法通过将时间序列分成若干段,并从每个分段中提取一个特征向量,从而用一个特征向量集作为该时间序列的逻辑表示。在此基础上,采用时间弯曲距离作为相似模型,提出了一种改进的KMP算法作为检索方法。此算法能够快速挖掘出时序数据库中与给定查询序列相似的所有(子)序列。该算法具有较高的效率。

In this paper, a new data representation for time series is presented, which can support similarity search very efficiently in a time series database. First, each sequence is divided into several segments. Second, a feature vector is extracted from each segment and let a set of such feature vectors as a logical representation of a sequence. Finally, the time warping distance is used as similarity model and introduce a modified KMP algorithm to retrieve all the sequences or subsequences that are similar to the query sequence given by users. The experimental results prove that this approach is efficient and practical.