一种时间序列相似搜索中提前终止效率的估算方法  

Estimate on the Effects of Early Abandon Technique in Time Series Similarity Search

作　　者：李俊奎[1] 王元珍[1] 李海波[1] 左琼[1] 

机构地区：[1]华中科技大学数据库与多媒体研究所,武汉430074

出　　处：《计算机科学》2009年第1期114-117,共4页Computer Science

基　　金：国家发展与改革委员会"安全智能数据整合平台开发及产业化"项目(项目编号[2005]538号)资助

摘　　要：提前终止(Early Abandon)是在受限的相似搜索中的一项技术,在提高时间序列相似搜索的效率,减少冗余计算中取得成功应用。但是以往的工作中提前终止的效率往往都只是通过大量的实验测试来体现,而缺少一种理论化的方法。从理论上提出了一种对提前终止技术的实际效率的估算方法,采用统计概率的方式分析了提前终止技术在时间序列相似搜索中的效率,同时对理论结果进行了实验验证。实验结果表明,理论上的估计方法在一定程度上可以估算出提前终止的效率,为时间序列相似搜索的实际效率计算提供了理论工具。Early abandon is one of the techniques in the constrained similarity search,and has found great success in accelerating time series similarity search, as well as reducing the redundant computations. However, previous works on early abandon were focused on the empirical experimental demonstrations on the effects of the technique, while no theo- retical analysis is available. A theoretical estimate method on the effects of early abandon was proposed, which adopts the statistical analysis in the process. Substantial experiments were performed to evaluate the results of the estimate. The experimental results show that the estimate can get the value of the effects in most cases, and can be applied in the real efficiency calculation of time series similarity search.

关 键 词：时间序列 相似搜索 提前终止 概率 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论] O211.61[自动化与计算机技术—计算机科学与技术]