排序的子序列相似查询方法  

Ranked subsequence similarity search

作　　者：朱鹤[1] 赵威[1] 余靖[1] 金顺福[1] 刘国华[1] 

机构地区：[1]燕山大学信息科学与工程学院,河北秦皇岛066004

出　　处：《燕山大学学报》2009年第5期417-421,共5页Journal of Yanshan University

基　　金：国家自然科学基金资助项目(60773100);国家"十一五"科技支撑计划资助项目(2006BAK05BO2);河北省自然科学基金资助项目(F2009000475)

摘　　要：时间序列数据的高维性是影响数据查询代价的主要因素,降维技术是时间序列数据查询优化的有效手段。原有降维技术近似体积的无界性,造成索引阶段不能充分实现点过滤,影响了查询效率。首先,利用近似体积有界的非线性降维技术解决了点过滤问题。然后,引入提前终止技术,减少了原始序列距离计算阶段的冗余计算。在此基础上,提出排序的子序列相似查询算法。实验结果表明,排序子序列相似查询方法具有较高的效率。High dimensionality of time series data cause high query cost. Dimensionality reduction on the data is an effective way ofqueryoptimization. The approximation volume ofproposed dimensionality reduction is unbounded, so the algorithm can not effectively filter the point in the index. First, a new non-linear dimensionality reduction is used to resolve the problem. Second, Early abandon technique is introduced to further improve efficiency and reduce redundant computation. Then on these basis, ranked subsequence similarity search algorithm is proposed. The experimental results show that ranked algorithm has higher efficiency.

关 键 词：排序 非线性降维 提前终止技术 紧密下限 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]