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

发布时间：2018-03-30 04:35

本文选题：数据流　切入点：动态时间扭曲　出处：《计算机学报》2017年10期

【摘要】：对于滑动窗口下不具有全局约束机制的数据流Disjoint查询精确处理问题进行了研究,在现有FSM算法基础上提出了一种具有增量计算特征的查询处理算法DQPIC.该算法使用FSM算法处理第一个窗口中的数据流成员,同时保留了该窗口上的查询结果和窗口所对应STWM的最后一个列向量,除此之外还需要保留窗口STWM中所有列向量第curbound.highest个成员DTW路径的起始位置、距离值以及该成员在STWM中对应列向量的dmin值和候选查询结果这些信息.从第二个窗口开始,继续使用FSM算法处理窗口成员,同时也保留和第一个窗口一样的信息.在这个过程中,当处理相邻窗口中相同数据流成员时,通过比较该成员在前后两个窗口中分别对应的保留信息是否相同,可以确定算法有无继续处理剩余相同数据流成员的必要,能够在前一个窗口查询结果基础上增量地获得当前窗口查询结果.基于公用数据样本SST与Maskedchirp的仿真实验验证了该算法的有效性.提出的算法与现有其他算法执行结果相同,在空间开销增加1.12~3.27倍情况下,可以实现时间效率2.5~25倍的提高,对于与大窗口下的Disjoint查询相关应用场景,具有更好的时间效果.
[Abstract]:In this paper, the problem of accurate processing of Disjoint queries in data flow without global constraint in sliding window is studied. A query processing algorithm DQPIC-based on the basis of existing FSM algorithms is proposed, which uses the FSM algorithm to process the data flow members in the first window. The query results on the window and the last column vector of the STWM corresponding to the window are retained, in addition to the starting position of the DTW path of the curbound.highest member of all column vectors in the window STWM. The distance value, the dmin value of the member's column vector in the STWM, and the result of the candidate query. From the second window, continue to use the FSM algorithm to process the window member, It also retains the same information as the first window. In this process, when processing the same data flow member in the adjacent window, we compare whether that member corresponds to the same reservation information in the two windows before and after, You can determine whether the algorithm is necessary to continue processing the remaining same data stream members, The current window query results can be obtained incrementally on the basis of the previous window query results. Simulation experiments based on common data samples SST and Maskedchirp verify the effectiveness of the proposed algorithm. When the space cost is increased by 1.12 ~ 3.27 times, the time efficiency can be improved 2.5 ~ 25 times, and it has better time effect for the application scenarios related to Disjoint query under large windows.
【作者单位】：东北大学计算机科学与工程学院;郑州轻工业学院计算机与通信工程学院;
【基金】：国家自然科学基金(60903159,61173153,61402096,61501405) 中央高校基本科研业务费资助项目(N110818001,N100218001,N130504007,N120104001) 沈阳市科技计划项目(1091176-1-00) 国家“八六三”高技术研究发展计划基金(2015AA016005)资助~~
【分类号】：TP301.6

【相似文献】