一种基于B^+-tree索引的有效相似查询算法  

A kind of efficient similarity search algorithm based on B^+-tree index

作　　者：郭小芳[1] 叶华[2] 

机构地区：[1]江苏科技大学计算机科学与工程学院,江苏镇江212003 [2]江苏科技大学电子信息学院,江苏镇江212003

出　　处：《西北师范大学学报（自然科学版）》2012年第4期33-37,共5页Journal of Northwest Normal University(Natural Science)

基　　金：江苏省高校自然科学研究项目(10JKB520006)

摘　　要：提出了一种多元时间序列相似查询算法.在距离索引结构相似查询算法的基础上,利用主成分分析方法对多元时间序列进行降维,并对主成分进行聚类,在聚类质心与各类之间的范数所构成的一维空间上,对聚类建立B+-tree索引结构,然后利用k近邻查询算法查找出与查询序列最相似的k个MTS序列.实验结果表明,文中算法的候选比率与查询时间明显低于Muse算法,且候选比率与查询时间受聚类个数影响不大,说明文中算法具有一定的优越性.A multivariate time series similarity search algorithm is proposed.Distance-based index structure（Dbis） for similarity search,principal component analysis（PCA） method,and the principal component of MTS were clustered,and the MTS items were mapped into one dimensional space based on clustering centre of each partition,on B＋-tree indexing configuration,k MTS items were find out as most similar MTS sequences for given MTS sequence.The experimental results show that candidate ratio and query time of this algorithm was significantly lower than that of Muse algorithm,and the candidate ratio and querying time are not affected significantly by the number of clusters,the algorithm has certain superiority in comparison with other algorithm.

关 键 词：多元时间序列 主元分析 B+-tree索引 相似查询 

分 类 号：TP391.4[自动化与计算机技术—计算机应用技术]