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

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

提前终止(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.