一种滑动窗口下数据流Disjoint查询的增量处理算法

作     者：王少鹏 闻英友 赵宏 孟颍辉 WANG Shao-Peng WEN Ying-You ZHAO Hong MENG Ying-Hui

作者机构：东北大学计算机科学与工程学院沈阳110819 郑州轻工业学院计算机与通信工程学院郑州450002 

出 版 物：《计算机学报》 (Chinese Journal of Computers)

年 卷 期：2017年第40卷第10期

页      面：2381-2403页

核心收录：

学科分类：0810[工学-信息与通信工程] 0808[工学-电气工程] 0839[工学-网络空间安全] 08[工学] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 081202[工学-计算机软件与理论] 

基　　金：国家自然科学基金(60903159 61173153 61402096 61501405) 中央高校基本科研业务费资助项目(N110818001 N100218001 N130504007 N120104001) 沈阳市科技计划项目(1091176-1-00) 国家"八六三"高技术研究发展计划基金(2015AA016005)资助~~ 

主　　题：数据流 动态时间扭曲 Disjoint查询 滑动窗口 增量计算 

摘      要：对于滑动窗口下不具有全局约束机制的数据流Disjoint查询精确处理问题进行了研究,在现有FSM算法基础上提出了一种具有增量计算特征的查询处理算法DQPIC.该算法使用FSM算法处理第一个窗口中的数据流成员,同时保留了该窗口上的查询结果和窗口所对应STWM的最后一个列向量,除此之外还需要保留窗口STWM中所有列向量第***个成员DTW路径的起始位置、距离值以及该成员在STWM中对应列向量的dmin值和候选查询结果这些信息.从第二个窗口开始,继续使用FSM算法处理窗口成员,同时也保留和第一个窗口一样的信息.在这个过程中,当处理相邻窗口中相同数据流成员时,通过比较该成员在前后两个窗口中分别对应的保留信息是否相同,可以确定算法有无继续处理剩余相同数据流成员的必要,能够在前一个窗口查询结果基础上增量地获得当前窗口查询结果.基于公用数据样本SST与Maskedchirp的仿真实验验证了该算法的有效性.提出的算法与现有其他算法执行结果相同,在空间开销增加1.12~3.27倍情况下,可以实现时间效率2.5~25倍的提高,对于与大窗口下的Disjoint查询相关应用场景,具有更好的时间效果.