基于适应性分段估计的数据流上在线相似性搜索

摘要

相似性搜索在股票交易行情,网络安全,传感器网络等众多领域应用广泛。由于这些领域中产生的数据具有无限的、连续的、快速的、实时的特性,所以,需要适合数据流上的在线相似性搜索算法。本文首先,在具有或不具有全局约束条件下,分别提出了没有索引结构的DTW下限函数LB_seg_WFglobal和LB_seg_WF,它们是一种分段DTW技术,能够处理数据流上的非等长序列问在线相似性匹配问题。然后,为了进一步提高LB_seg_WFglobal和LB_seg_WF的近似程度,提出了一系列的改进方法。最后,针对流上使用LB_seg_WFglobal或LB_seg_WF,可能会出现连续失效的情况,分别提出了DTW的下限函数LB_WFglobal(具有全局约束条件)和上限函数UB_WF、下限函数LB_WF(不具有全局约束条件),通过增量方式,快速估计DTW,大大减少估计DTW的冗余计算量。通过理论分析和统计试验,验证了本文方法的有效性。