第39卷  计  算  机  学  报  Vol.39 2016 论文在线出版号  No.176  CHINESE JOURNAL OF COMPUTERS  Online Publishing No.176 ——————————————— 本课题得到国家自然科学基金项目(No. 60903159, 61173153,61402096, 61501405)、中央高校基本科研业务费资助项目(No. N110818001, N100218001, N13050400 7, N120104001)、沈阳市科技计划项目(No.1091176-1-00)、国家“八六三”高技术研究发展计划基金项目(2015AA016005)资助.王少鹏(通讯作者)，男，1984年生，博士研究生，主要研究领域为数据流、事件流、数据挖掘.E-mail: wangshaopeng1984 @163.com.  闻英友，男，1974年生，博士后，副教授，主要研究领域为下一代网络、无线传感器网络.E-mail: wenyy@neusoft.com.  赵宏，男，1954年生，博导，教授，主要研究领域为网络管理、多媒体. E-mail: zhaoh@neusoft.com.  孟颍辉，男，1984年生，博士，讲师，主要研究领域为无线传感网络，传感器定位.E-mail: yinghuimeng @zzuli.edu.cn. 一种滑动窗口下数据流Disjoint查询的               增量处理算法 王少鹏1)  闻英友1)  赵宏1)  孟颍辉2) 1)(东北大学  计算机科学与工程学院,  沈阳  110819) 2)(郑州轻工业学院  计算机与通信工程学院,  郑州  450002) 摘  要  对于滑动窗口下不具有全局约束机制的数据流Disjoint查询精确处理问题进行了研究，在现有FSM算法基础上提出了一种具有增量计算特征的查询处理算法DQPIC．该算法使用FSM算法处理第一个窗口中的数据流成员，同时保留了该窗口上的查询结果和窗口所对应STWM 的最后一个列向量，除此之外还需要保留窗口STWM 中所有列向量第curbound.highest个成员DTW路径的起始位置，距离值以及该成员在STWM中对应列向量的dmin值和候选查询结果这些信息．从第二个窗口开始，继续使用FSM算法处理窗口成员，同时也保留和第一个窗口上一样的信息．在这个过程中，当处理相邻窗口中相同数据流成员时，通过比较该成员在前后两个窗口中分别对应的保留信息是否相同，可以确定算法有无继续处理剩余相同数据流成员的必要，能够在前一个窗口查询结果基础上增量地获得当前窗口查询结果．基于公用数据样本SST与Makedchirp的仿真实验验证了该算法的有效性．提出的算法与现有其他算法执行结果相同，在空间开销增加1.12~3.27倍情况下，可以实现时间效率2.5~25倍的提高，对于与大窗口下的Disjoint查询相关应用场景，具有更好的时间效果． 关键词  数据流；动态时间扭曲；Disjoint 查询；滑动窗口；增量计算 中图法分类号  TP311   论文引用格式 王少鹏，闻英友，赵宏，孟颍辉，一种滑动窗口下数据流Disjoint查询的增量处理算法，2016，Vol.39：在线出版号  No.176 WANG Shao-Peng，WEN Ying-You，ZHAO Hong，MENG Ying-Hui，An Incremental Processing Algorithm about Disjoint Query Based on Sliding Window over Data Stream，Chinese Journal of Computers,2016, Vol.39: Online Publishing No.176 An Incremental Processing Algorithm about Disjoint Query Based on Sliding Window over Data Stream WANG Shao-Peng1)  WEN Ying-You1)   ZHAO Hong1)    MENG Ying-Hui2) 1)(School of Computer Science and Engineering, Northeastern University, Shenyang 110819)   2)(School of Computer and Communication Engineering, Zhengzhou University of Light Industry, Zhengzhou 450002)  Abstract  With the fast development of internet of things technology, more and more applications are producing data stream continueslly. In order to obtain the knowledge in this kind of data, data stream mining technology is studied widely, and is great significant. All those obtained knowledge can be taken as our guildeline for action. The similarity query over data stream is a very important one in all researches related to the data stream mining 网络出版时间：2016-11-29 12:28:52网络出版地址：http://www.cnki.net/kcms/detail/11.1826.TP.20161129.1228.002.html2  计  算  机  学  报  2016年 technology,  and  has  been  essential  in  many  applications,  like  precision  agriculture,  and  environmental monitoring. In  all  researches which  is  about the  similarity  query  over  data  stream, Disjoint  query  has  played  a very important role, and can get all subsequences which are similar to the given query sequence in data stream. All these obtained subsequences are local minimal. However, the current researches did not focus on the Disjoint query based on the sliding  window over data stream. In order to resolve  the problem of precise Disjoint query processing based on the sliding window without global warping constraints over data stream, an effective query processing algorithm DQPIC which has characteristic of incremental calculation is proposed based on the current FSM  algorithm.  This  algorithm handles  the data stream  elements  in  the  first  sliding  window  with the  FSM algorithm, and preserves query results and the last colomn vector of the STWM matrix about the window over data stream. In addition, some other kinds of informations about the every column vector of STWM matrix are also needed  to  be reserved, such  as  the  start  position  and distance  value  of  the  DTW  road about the  element whose  index  is curbound.highest in these  column  vectors of STWM matrix, the dmin value, and  the  candidate query  result. Beginning  from  the  second  sliding  window, the  FSM  algorithm  is  still  be  taken  for  the  window elelements processing by the DQPIC algorithm, and the same informations as those retained in the first window are also still needed to be reserverd. However, in this procedure, when all data stream elements which located in two  both adjacent  windows over  data  stream are  processed,  the DQPIC algorithm can  determine whether  the remaining  elements  of  them  still  need  to be  processed by the FSM algorithm based  on comparison  of those informations which are preserved respectively about  the colomn  vector  corresponding  to  the same processing data stream element of two matrixes about these two sliding windows. By doing this, the algorithm can get query results  of  current  window  based  on those  ones  of  the adjacent  last window  over  data  stream, and  has  the characteristic  of  incremental calculation. The experimental  results based  on  common  data  sample  SST  and Maskedchirp demonstrate  the proposed  algorithm is  effective．It has  the  same  results  as  the  current other algorithms,  and  can  improve  the  time efficiency by  2.5~25  times  at  the  cost  of  increment  of  space  cost  by 1.12~3.27 times. In the application scenarioes which are related to the Disjoint query based on the larger sliding window over data stream, the DQPIC algorithm has better performance in the time. Key words  data stream; dynamic time warping; Disjoint query; sliding window; incremental calculation   1  引言 Disjoint查询作为基于DTW的数据流子序列相似性查询中非常重要的一类，可以帮助用户从数据流中获取有用信息，在很多应用领域都有着非常重要的作用[1-10]．图1给出了Disjoint查询的过程描述．其中(a)是一个查询序列，(b)中实线条描述了一个数据流序列．Disjoint查询可以求得数据流序列中与查询序列相似的所有不相交子列，而且每个子列都是与该子列相交且满足查询条件的子序列中的局部最优序列，如图中的两个子序列subseq1 与subseq2就是当前数据流序列中Disjoint查询结果．                                (a)                                        (b) 论文在线出版号  No.176  王少鹏等：一种滑动窗口下数据流Disjoint查询的增量处理算法  3                    图1    Disjoint查询 在当前有关Disjoint查询的研究中，较少关注滑动窗口下Disjoint查询的处理机制．而这类查询却有着较多的应用需求，比如在精细农业中，相关领域专家通过对大量样本的分析，可以得到适宜害虫孵化的温度取值走势，将其定义为查询序列．为了了解一定时间范围内农作物可能发生虫害的情况，可以将查询序列与该时间范围的窗口序列作Disjoint查询；又如在工业生产领域，通过对封装到生产过程的传感器所捕获得一定时间范围内流式数据与相应的异常数据模式作相似性查询，可以判断该时间范围内工业生产过程中的异常发生情况，进而采取相应措施减少因异常发生而异致的人力，物力损失；再比如在环境监测领域，通过对藻类污染数据的分析可以得到适宜于该藻类生长的温度或湿度序列，以它们为查询序列与一定时间范内负责监控的相应传感设备所检测到的流式数据做作Disjoint查询，该查询结果对于我们了解水域中藻类污染发生的可能性有重要的参考价值．图2中给出了滑动窗口下Disjoint查询的具体说明．    图2    滑动窗口下Disjoint查询 其中X是一个数据流序列，而Y是一个长度为m的查询序列，window1与window2是两个相邻的滑动窗口，subseq1与subseq2是window1上的两个Disjoint查询结果，滑动窗口下的Disjoint查询就是要求得window1之后类似于window2一样的每个窗口上的Disjoint查询结果． 当前专门针对滑动窗口下数据流Disjoint查询的研究很少，文献[9]对该问题进行了研究，提出了一种基于边界路径技术的查询处理算法，该算法在产生和不产生查询结果的窗口上分别给出了边界路径，伪边界路径以及与之相关的创建元素的概念，通过比较前一个窗口上的创建元素在当前窗口中所对应的扭曲路径与前一个窗口上的边界路径或伪边界路径是否相同，来确定基本算法对于相邻2个窗口中相同数据流成员的处理量，能够增量地得到当前窗口上的Disjoint查询结果．但该算法忽略了在使用基本算法处理相邻两个窗口中位于创建元素之前相同数据流成员时存在的冗余运算． 本文同样对滑动窗口下的Disjoint查询处理问题进行了研究，文中将这种查询命名为DQ-SW查询(Disjoint  query  based  on  sliding  window)．对于naive算法处理DQ-SW查询的过程进行了分析和研究，提出了具有增量计算特征的DQ-SW查询处理算法(DQ-SW  query  processing  algorithm  with incremental calculation，简称DQPIC)．该算法能够在前一个窗口查询结果的基础上增量获得当前窗口的查询结果，与现有算法相比，很好地减少了查询处理的时间开销．特别与文献[9]中的FSDQ算法相比，在处理相邻两个窗口上相同数据流成员的时候，DQPIC算法无需每次都对创建元素前的所有数据流成员进行处理，即可得到窗口上的查询结果，具有更好的时间效率．文章实验部分证明了该算法是有效的．本文的第2节回顾了相关工作；第3节介绍了相关预备知识，包括Disjoint查询，Spring算法，FSM 算法以及文中要解决问题的形式化定义；第4节针对naive算法在处理DQ-SW查询时不具有增量计算的缺点，提出了DQPIC算法，并着力介绍了该算法的理论依据；第5节给出了实验结果与分析；第6节总结全文，并说明了下一步的研究方向． 2  相关工作 越来越多研究证明DTW是最好的距离测度函数[11]．当前与基于DTW的数据流子序列相似性搜索相关的研究可分为如下几类：1)将数据流上的子序列长度固定，然后得到这些子列中与查询序列最相似的序列[12-13]，或者是判断这些子序列是否与查询序列相似[14-18]．2)Disjoint查询，即用于得到数据流中与查询序列相似的所有不相交子列，而且每个子列都是与该子列相交且满足查询条件的子序列中的局部最小序列[1-10]．和第一类研究相比，Disjoint查询并不需要分割原始数据流序列，且得到的查询结果不会相交且是局部最优．自从Sakurai在2007年的ICDE 会议上给出了Disjoint查询的定义，并提出了相应处理算法Spring之后，很多研究者都在此基础上做了大量的研究工作． 当前有关这类查询的研究按照查询结果的状4  计  算  机  学  报  2016年 态，可分为精确Disjoint查询和近似Disjoint查询2类．在精确Disjoint查询方面，按照是否考虑全局约束机制又为了2类，一类不考虑全局约束机制，如Sakurai等在[1]中提出了Spring算法，该算法是第一个对该查询进行处理的算法；Zou 等改进了Spring算法，提出了FSM算法[2]，该算法能有效地减少Spring算法的运算量；Kashyap等对Spring算法进行了改进，提出了eHaarSubseq 算法[3]．该算法中使用了基于haar小波的eHaar技术，可以提前将数据流中与查询序列不相似的子列从中删除，然后对数据流中剩余部分成员与查询序列执行Spring算法，与原来Spring算法相比，时间效率更好；Gong 等同样对于SPRING 算法进行了改进，提出了NSPRING算法[10]，该算法使得Spring算法支持所处理数据的正交化操作.  另一类是考虑全局约束机制，如Niennattrakul等在文献[4-5]中对Spring算法中的全局约束机制与归一化处理问题分别作了研究，提出了ASM与MSM算法，可以更合理地处理数据流的子序列相似性搜索问题；Wang等在[6]中结合FPGA技术提出了一种Disjoint查询处理方法，该方法分为算法软设计与算法的FPGA实现2个部分．在算法软设计中，作者提出了混合下界函数LB_pDTW来估计Disjoint查询中DTW距离的下边界．该算法会先使用下界函数去掉数据流中不符合查询条件的子序列，然后在此基础上再使用Spring算法进行处理，不过该算法的效果极大地依赖于FPGA技术的实现；近似Disjoint查询通常会以一定的精度为代价，换得查询执行在时空方面的效率，比如[7-8]，其中[7]中的EBSM算法是Athitsos等在Spring算法基础上提出的，与Spring算法相比，DTW距离的计算次数要少很多，但也付出了查询结果不够精确的代价；Zhou 等在[8]中，提出了一种数据流维数约减技术NPLA，然后在此基础上给出了Disjoint查询的处理算法．相比于使用了PAA维数约减技术的Spring算法，该算法具有时间优势.   还有些研究虽然涉及到了Disjoint概念，但其研究的本质与我们研究的内容并不相同，如文献[19-20]关注的是数据流外包查询认证．其中涉及的Disjoint查询与我们研究的数据流Disjoint查询并不是一类查询方式．前者主要为了减少client多个查询的认证代价，将它们中重合的部分进行解构，使其成为不相交的子查询(Disjoint查询)，通过对这些子查询结果的union操作可以得到最初client查询的认证结果，这样可以减少操作代价．总体来看它们中所谓的Disjoint涉及到两个方面，一个是不同数据流间的Disjoint(即不相交)，另一个是多个查询所针对的对象之间尽量解构为不相交的情况．而我们研究的是数据挖掘中的相似性查询，其中Disjoint查询指的是数据流中的查询结果间是不相交的，而且每一个结果都是与之相交的子列中的局部最小值，所以这两类研究是不同的．文献[21]关注的是数据流管理系统（DSMS）中的查询语言方面存在的问题，定义了一些新的数据流操作符和相应的查询语言使用结构．其中有些概念与我们的研究在命名上一样，但实质并不相同．如它们对于模式的定义是基于数据流成员使用正则表达式来描述的．主要关注的是数据流中不同成员间的关系，也就是说它们的模式匹配是指的是到来的数据流成员满足正则表达式．这与我们的相似性查询定义不同；另外文献中的Disjoint  union 操作符是对于多个数据流的操作，其实质与关系数据库中union操作符相类似，这与我们Disjoint查询的定义不同．         值得注意的是在前面与我们所关注的Disjoint查询相关的研究中，它们所得到的查询结果都是从第一个处理的数据流成员开始，直到要处理的数据流成员被处理完为止，整个数据流上的Disjoint查询结果．这个处理过程中随着数据流成员的不断到来，数据流上Disjoint查询结果也在持续产生，其间并不涉及数据流成员的删除操作，相关算法不断地处理新到来的数据流成员，以得到新的Disjoint查询结果．但正如第一部分所述，有时候我们可能会对滑动窗口下Disjoint 查询的结果产生兴趣，而这样的Disjoint查询对数据流上每一个滑动窗口都需要重新执行，在窗口滑动的过程中会涉及到新数据的进入与旧数据的删除操作．王少鹏等人在文献[9]中对滑动窗口下数据流的Disjoint查询处理问题进行了研究，提出了一种FSDQ算法，但该算法忽略了在使用基本算法处理相邻两个窗口中位于创建元素之前相同数据流成员时存在的冗余运算． 总体来看，当前有关滑动窗口下数据流Disjoint查询处理问题的研究并不多，仅有的方法也存在冗余运算．得到一种更有效的处理方法是本文研究目的．需要说明的是在我们研究中，暂不考虑查询全局约束机制和对数据的正交化处理，主要对滑动窗口下数据流精确Disjoint查询处理问题进行研究． 论文在线出版号  No.176  王少鹏等：一种滑动窗口下数据流Disjoint查询的增量处理算法  5 3  预备知识 3.1    Spring算法 Spring算法是Yasushi Sakurai提出的第1个用来处理数据流Disjoint查询问题的算法．该算法有2个特点：1)提出了star padding 思想；2)使用了子序列时间扭曲矩阵STWM．其中前者为查询序列加“*”前缀，在求得查询序列与数据流子序列的DTW距离取值时，使用新查询序列代替旧查询序列．计算过程中规定“*”成员与任何数据流成员距离为0，这样原查询序列中第1个成员在STWM中对应行向量成员取值的计算只会涉及到该查询序列成员与对应数据流成员间的计算，所以可将数据流中每个成员作为子序列起点情况考虑进去，最终实现只用1个时间扭曲矩阵获得数据流中Disjoint查询结果的目的．STWM是为了配合star  padding思想而设计的数据结构，主要目的在于获得结果子序列起点位置．STWM中(t,i)成员含有2个成员：d(t,i)和sp(t,i)，它们的意义是X上sp(t,i)与t 之间的数据流序列与Y中长为i 的查询序列前缀之间的距离值为d(t,i)，该值也是X上长为t 的数据流前缀与Y中长为i 的查询序列前缀之间执行相似性匹配时的最小DTW距离值．这2个成员取值的计算会按如下公式进行． s e e( ( ), ) ( ) min( ( , )) :, DXt t Y d t m d t m ==，                  (1) best( , ) ( )ti d t i dist x y d =+-，                            (2)   ( )( )( )best,11,1, 1minddidiittdt=----ìïíïî，                                    (3)  ( ) ( ) ( ) , 0 0, 0, . 1 , 1 d t d i t n i m = = ¥ = = LL(4)                                 ( )( ) ( )( ) ( )( ) ( )bestbestbest1, 1,1, 1 1, 1, 1 , 1,,,,sp t i d t i dsp sp t i d t i dsp t i d t i dti- - =- - - - =- - =ìï=íïî  .          (5) Spring算法会在STWM每个列向量构建过程中得到Disjoint查询结果，有关该算法详尽描述可见文献[1]．另外本文中所有DTW距离都使用L1形式[2]距离函数，当然亦可扩展为其他距离函数形式． 3.2  Disjoint查询 定义1[1].  Disjoint  查询(Disjoint  query).  假定数据流X的长度为n，Y是一个长度为m的查询序列，epsilon为相似阈值，X(tstart:  tend)是数据流X中起止时间分别为tstart到tend的子序列，Disjoint查询是要得到X的子序列集Srange，序列集中的每个成员要满足如下的条件： 1)  如果X(tstart:tend)ÎSrange , 则有D(X(tstart: tend),Y)£epsilon； 2)  对于X上任意与X(tstart:tend)相交的子序列X(jtstart: jtend)，如果D(X(jtstart: jtend),Y) £ epsilon，一定有D(X(tstart: tend),Y)£D(X(jtstart: jtend),Y)； 3)  如果X(tstart: tend), X(tstart1: tend1)ÎSrange，则这两个序列要满足X(tstart: tend)Ç X(tstart1: tend1)=Æ. 其中D函数用于计算两个序列的DTW测度函数值，总得来说Disjoint查询就是要得到X上与Y相似但不相交的所有子列．该查询所使用的数据流模型为界标窗口模型． 3.3  FSM算法 FSM算法是一个由邹鹏等基于Spring算法提出的同样用于处理数据流环境下Disjoint查询的算法．同Spring算法不同的是，该算法采用了一种边界技术，最大程度地减少STWM构建过程中不必要的成员计算，以及相关的比较操作．具体来说，该算法分别用curbound.lowest 与curbound.highest保留STWM中正在被处理列向量的第一个和最后一个d值小于等于epsilon的成员位置；同时也分别用pribound.lowest与pribound.highest保留相邻前一个列向量中第一个和最后一个d值小于等于epsilon的成员位置．在求得STWM中正在被处理列向量所有成员d值的过程中，如果正在处理的成员d值大于epsilon ，假设此时前一列 向 量 的pribound.highest为0，则无需计算当前列向量所有剩余成员取值；否则当这个成员的位置小于pribound.lowest 时，则当前向量上该成员位置与pribound.lowest之间的所有成员d值都无需计算，直接处理索引为pribound.lowest的成员即可；当该成员的位置大于pribound.highest+1时，则无需计算当前列向量所有剩余成员的d值，处理当前向量到此结束；当该成员位置大于等于pribound.lowest，且小于等于pribound.highest+1时，需要按Spring算法计算成员的d值．这个过程也要记录下当前列向量的curbound.highest 与curbound.lowest，当处理完该向量后，需要将curbound取值赋予pribound，接着开始处理STWM中下一个数据流成员所对应的列向量．有关FSM算法的详细情况可见文献[2]．   6  计  算  机  学  报  2016年 3.4  问题定义 定义2.数据流.数据流X被看作连续到达的离散、无限的元组序列，表示为x1, x2,…, xt-1, xt ,…,其中t 为时间，本文中设数据流速度恒定． 定义3．基本窗口EW与滑动窗口SW．EW是定长时间内连续到达的数据流序列，即有EW={xi, xi+1, …, xi+m}，其中m是基本窗口大小，表示为|EW| =m．SW对应SWsize 个连续相邻基本窗口序列，即有SW={EWj, EWj+1, …, EWj+SWsize}，其中SWsize为滑动窗口大小，表示为|SW|=SWsize，且有"k，lÎ[j, j+ SWsize]，如果k¹l，有EWkÇEWl=Æ.  当窗口已满， SW会随数据流成员到来，以EW为单位不断滑动． 定义4.DQ-SW 查询(Disjoint  query  based  on sliding window). "Y，epsilon，SWsize，|EW|,  令seqSW ={SW1, SW2, SW3, …, SWn}是我们关注的数据流上n个连续的滑动窗口序列,  其中nÎ ，SWn是seqSW中第n个窗口．对于每个SWn，DQ-SW查询就是求得其上数据流成员与Y的Disjoint查询结果，这也是本文着力要解决的问题． 4  具有增量计算特征的DQ-SW查询处理算法   表1说明了文中所用到的变量和表达式所代表的含义． 表1   变量和表达式含义说明 变量和表达式  含义 candidate  dmin FSM 算法中的参数，是STWM中每个列向量构造完成后的候选查询结果； FSM算法的参数，是candidate的距离；   Paracur  DQPIC 算法中对应于当前窗口的参数； Preserve_FSM_P    tempara  基于相邻前一窗口最后一个成员对应列向量及其参数对当前窗口最后一个基本窗口EW中的成员执行FSM算法，并保留DQPIC算法中所需要的相关参数；   用于临时存放滑动窗口SW中一个数据流成员对应的参数，这些参数都是DQPIC算法中用到的； Paracur,v Paracur(index)  hbound  Paracur中与当前窗口成员v对应的参数； Paracur中与当前窗口索引为index+1的基本窗口EW中成员对应的参数； DQPIC算法中与当前窗口SW每个成员对应的参数，用于存放STWM中与该  Vhbound 成员对应列向量相关的curbound.highest； 与滑动窗口SW每个成员相关的参数，用于存放STWM 每个列向量中索引为hbound的成员d值；   winelenum  从DQPIC算法执行开始进入到滑动窗口SW中的EW总数；   Paracur.lastvec   resultcur getresult  Paracur 中的参数，包括与当前窗口相关的STWM中最后一个列向量，以及与之相关的参数；   当前窗口的查询结果； DQPIC算法在处理相邻窗口相同数据流成员的过程中，会寻找一个在两个窗口中相关参数都相同的成员，在找到该成员后，getresult会从resultcur中得到其他相同数据流成员在被DQPIC算法处理过程中产生的查询结果； 4.1  naive算法 由Spring算法可知，解决DQ-SW查询最直接方法即在每个数据流窗口上执行Spring算法．但由文献[2]可知，这种算法处理Disjoint查询时存在冗余运算．邹鹏等在该文献中所提出的FSM 算法，不仅与Spring算法执行效果相同，还大大减少了这种冗余运算，所以我们也能通过在每个数据流窗口上执行FSM 算法解决这类查询处理问题，而且这种方法比第一种方法冗余计算量少，本文把这种方法称为naive算法．由FSM算法可知，每个窗口上 naive 算法查询结果是在该窗口上m´ (|EW|´SWsize)阶矩阵STWM构建过程中产生的，而该矩阵的构成则是循环使用了两个大小为m的列向量． 4.2  具有增量计算特征的DQ-SW查询处理算法 naive算法需要在每个窗口上重新执行FSM算法以得到该窗口上DQ-SW查询结果，不同窗口上查询结果的获得过程彼此独立，所以算法不具有增量计算的特点，而这个问题的存在使得该算法执行效率并不是很高．为了解决该问题，我们在这部分提出了具有增量计算特征的DQ-SW查询处理算法DQPIC．具体来说，首先给出该算法理论依据的直观描述；其次，对于算法理论依据的正确性进行了严格证明；接着基于该理论依据给出了DQPIC算法的详细执行步骤；最后分析了算法的时间、空间复杂度．         论文在线出版号  No.176  王少鹏等：一种滑动窗口下数据流Disjoint查询的增量处理算法  7 4.2.1    DQPIC算法理论依据的直观描述 为便于对比分析，我们使用了文献[1-2]中的查询实例．假设数据流X={11，20，3，6，10，14，15，3}，查询序列Ｙ={2，6，9，13，15，4}，epsilon=15，SWsize=4，|EW|=2，图3中(a)(b)虚线区域分别给出相邻2个窗口在执行完FSM算法后的STWM，我们分别将其命名为STWM1 与STWM2 与；2 个STWM中列向量内横线背景和竖线背景成员的数字分别标出了该向量中highest与lowest 成员，而它们在向量中索引分别是该向量中highest与lowest变量取值．                            (a) STWM1                                                               (b) STWM2 图3    STWM1  和STWM2的示例 在图3的STWM中，每个成员有2部分取值，括号内外分别为起始位置sp与成员d值，每个列向量上面是按照FSM 算法处理完该向量后得到的dmin值．通过对比STWM1与STWM2中成员取值，可以发现：EW2，EW3，EW4 中数据流成员在两个矩阵中对应列向量成员取值完全相同．而由FSM算法可知，STWM中每个列向量成员取值只与相邻前一个列向量及与该向量相关参数取值有关，所以根据x3在两个矩阵中对应列向量成员取值，以及相关参数取值相同，就可推得EW2中其他数据流成员，以及EW3，EW4中所有数据流成员对应列向量取值，以及在这些列向量成员取值计算过程中产生的查询结果是相同的．显然基于该思想处理DQ-SW查询比naive  算法的时间效率好．但这个思想应用前提是记录当前窗口STWM中每个列向量及其相关参数，还有与该向量相关的查询结果取值情况，这样在求相邻下个窗口上查询结果时，处理两个窗口相同数据流成员可用“边处理，边比较”方式进行． 具体来说在得到每个相同数据流成员在下一个窗口中对应的列向量后，将该向量与同一数据流成员在当前窗口中对应的列向量取值进行比较，如果两个列向量取值及对应参数取值完全相同，则不必处理其他相同数据流成员，因为这些成员在两个STWM中对应列向量取值，以及在这个过程中产生的查询结果完全相同，我们只需将这些成员在当前窗口处理过程中产生的结果直接拿来即可．当然这个时候若要得到相邻下一个窗口上的完整查询结果，还需要在当前窗口最后一个列向量及相关参数取值的基础上对下一个窗口新加入的EW中成员执行FSM算法． 但这种方法缺点明显，在保留信息中会涉及到每个列向量成员取值，空间开销大．若能以较少保留信息表征要比较的这部分内容，则可以极大改善该算法空间开销．我们在进一步观察后有个猜想，即能否以STWM每个列向量对应的highest以及与该值对应的成员取值来描述整个列向量成员取值信息，也即能否以相邻两个窗口任意相同数据流成员在这两个窗口中相关参数，以及该数据流成员在这两个STWM 中对应列向量的highest，和与highest对应的列向量成员取值相同，推出这两个窗口其他相同数据流成员在使用FSM 算法处理过程中构建的列向量成员取值，以及产生的查询结果也相同．结合图3就是能否以x3在STWM1与STWM2中处理完成后的相关参数相同，以及x3在这两个矩阵中对应列向量highest 值相同，和列向量中第highest个成员取值相同，推出x4~x8在两个矩阵中对应列向量成员取值，以及在这些列向量构建过程中产生的查询结果也相同．若可以，则设想成立．该猜想是DQPIC算法的理论基础．下面分析了它的正确性． 4.2.2  关于DQPIC算法理论依据的分析证明 为便于证明猜想，这部分先给出相关知识前提，接着基于分析证明了DQPIC算法的理论依据．       1)  知识前提 8  计  算  机  学  报  2016年 本部分内容主要包括DTW路径定义，以及以引理形式给出的相关性质；同时也包括基于此分析出的Spring算法中STWM成员取值与Disjoint查询结果间的关系，这个关系我们以定理形式呈． 令SMi 是滑动窗口SWi 上的成员在执行完Spring算法后得到的STWM，SVi,j 是SMi 中第j 个列向量．由Spring算法可知，该算法在确定矩阵中任一成员sp与d值时，需要得到该成员的dbest值，同时找到该dbest所在的矩阵成员．进一步由Spring算法可知，在确定矩阵成员sp与d值的过程中，每个成员的dbest所在成员都是唯一的．且每个成员的sp值与该成员dbest所在矩阵成员的sp值是相同的(可参考[1]与3.1部分)． 定义5．DTW路径．设I(i,j)是SVi,j 对应的数据流成员索引，则SVi,j 与该SWi 中的数据流成员xI(i,j)相对应．对于SVi,j 中任意成员SVi,j(t)，(由下而上的顺序)，如果该成员对应的sp值SVi,j(t).sp=p，则xp对应的向量SVi,u(其中u=j-(I(i,j)-p))中的第1个成员SVi.u(1)与SVi,j(t)之间一定存在一条路径(即扭曲路径)，路径上任意成员是该路径上相邻下个成员的dbest所在矩阵成员，我们把该路径称为SVi,j(t)在滑动窗口SWi 中的DTW路径，记为Ri,j(t)．而p被称为该路径的起始位置，记为Ri,j(t).sp． 同样为了便于对比分析，我们使用了文献[1-2]中的查询实例．X={11，20，3，6，10，14，15，3}，查询序列Ｙ={2，6，9，13，15，4}，epsilon=15，SWsize=3，|EW|=2，我们以X在第1个滑动窗口上的实例来说明DTW路径的概念，详情见图4．  图4  DTW路径示例 图4中虚线区域是SW1上执行完Spring算法后的STWM，矩阵中每个成员包括2部分取值，括号内 为 起 始 位 置 sp ， 括 号 外 为 成 员d值．SV1,3(1)~SV1,6(6)之间阴影部分成员构成了SV1,6(6)在滑动窗口SW1中的DTW路径R1,6(6)，该路径起始位置R1,6(6).sp为3．   引理1．对于SVi,j 中的任一成员SVi,j(t),1£t£m，该成员的起始位置sp 为p，(1)在向量SVi,u(其中u=j-(I(i,j)-p))中的第1个成员SVi.u(1)与SVi,j(t)之间一定存在唯一的DTW路径，路径上每个成员起始位置都为p；(2)对于SVi,j 中索引小于t 的成员来说，其sp值都大于等于p；而对于SVi,j 中索引大于t 的成员来说，其sp值小于等于p；(3)SMi 中位于路径Ri,j(t)下成员的sp值都大于等于p． 证明：(1)由定义5及Spring算法，结论(1)显然成立； (2)可以用反证法证明. "SVi,j中索引小于等于t(这里SVi,j中成员的索引是由下而上的顺序)的成员SVi,j(t1)，假设SVi,j(t1).sp=p1<p，则由结论(1)可知，在SVi.l(1)与SVi,j(t1)间一定存在一条DTW路径Ri,j(t1)，路径上所有成员起始位置都为p1，其中l=j- (I(i,j)-p1)．而由(1)可知，在SVi.u(1)与SVi,j(t)之间存在一条DTW路径Ri,j(t)，路径上每个成员起始位置都为p，其中u=j-(I(i,j)-p)．因为p1<p，所以有l<u，也即对于Ri,j(t1)与Ri,j(t)，有t1£t，且Ri,j(t1).sp< Ri,j(t).sp 成立，所以Ri,j(t1)与Ri,j(t)一定相交，由结论1可推得，位于交点位置的成员会有2个起始位置，p1与p，再由Spring算法可知这是不可能的，矛盾，所以假设不成立，即有SVi,j(t1).sp³SVi,j(t).sp =p成立．SVi,j 中索引大于t 成员的证明与此类似，不再赘述． (3)由定义5及Spring算法可知，Ri,j(t)在SVi.u与SVi,j 之间(包括SVi.u(1)与SVi,j(t))的每个列向量上都有成员，而STWM中位于这些成员位置下的矩阵成员构成了STWM 中位于Ri,j(t)路径下的成员．针对每个这类成员使用(2)中的反证法，容易推得结论成立．                                                    证毕． 我们仍以前面说明DTW路径时用到的数据流事例来说明引理1的内容，具体如图5所示．  图5  引理1说明 引理1的结论1告诉我们，STWM列向量中任一成员(也即STWM中任一成员)与数据流中索引为该成员起始位置的成员间一定存在唯一的DTW论文在线出版号  No.176  王少鹏等：一种滑动窗口下数据流Disjoint查询的增量处理算法  9 路径，如图5中SV1,2(4)~SV1,1(1)之间具有横线背景的成员所构成的路径即为SV1,2(4)在滑动窗口SW1中的DTW路径R1,2(4)，而SV1,3(1)~SV1,6(6)之间具有阴影背景的成员所构成的路径即为SV1,6(6)在滑动窗口SW1中的DTW路径R1,6(6)； 由引理1的结论2可知，对于矩阵中任一成员，考虑该成员所在列向量中索引值小于该成员索引值的成员，它们sp值都大于等于该成员的sp值；而对于该成员所在列向量中索引值大于等于该成员索引值的成员，它们的=sp 值都小于等于该成员的sp值，比如对于图5的SV1,2中索引大于SV1,2(4)在SV1,2 中索引值的成员(图中具有竖线背景的成员)，每个成员的sp值都小于等于SV1,2(4)的sp值1；而对于SV1,2中索引小于SV1,2(4)在SV1,2中索引值的成员(SV1,2中点虚线区域)，每个成员的sp值都大于等于SV1,2(4)的sp值1；又比如图5的SV1,6中索引小于SV1,6(5)在SV1,6中索引值的成员(SV1,6中点虚线区域)，每个成员sp 值都大于等于SV1,6(5)的sp值3． 引理１的结论3告诉我们，位于矩阵任一成员DTW路径下的所有矩阵成员，它们的sp值都大于等于该成员的sp值．比如位于图中R1,2(4)下的所有矩阵成员，它们的sp值都大于等于SV1,2(4).sp值，也即R1,2(4).sp值1；而位于图中R1,6(6)下的所有矩阵成员sp值都大于等于SV1,6(6).sp值3. 定理1．Spring算法在构建SMi 的过程中获得该窗口上的Disjoint查询结果，但这个查询结果与SMi 中d值大于epsilon的成员取值并没有关系，这个没有关系是指省略掉SMi 中d值大于epsilon的成员取值计算，并不会对查询结果产生影响． 证明．对于SMi 中的列向量SVi,j，如果该向量最后一个成员的sp值为p(即SVi,j(m).sp=p)，由引理1可知在xp对应列向量中的第一个成员SVi,p-i+1(1)与SVi,j(m)之间一定存在一条DTW路径Ri,j(m)，该路径在数据流中对应xp~xI(i,j)，同时路径上所有成员的sp值都为p．如果SVi,j(m).d£epsilon，则xp~xI(i,j)会被作为一个候选查询结果．之后每个列向量产生后，都会对该候选查询结果进行判定，以确定该查询结果是否是真正查询结果，而当新产生列向量的最后一个成员d值小于SVi,j(m).d时，该候选查询结果会被更新为新列向量最后一个成员所在DTW路径对应的数据流序列．所以我们要证明的包括两点：(1)省略掉SMi 中d值大于epsilon的成员取值计算后，SMi 中所有候选查询结果序列不会发生变化；(2)省略掉SMi 中d值大于epsilon的成员取值计算，不会影响对这些候选查询结果的判断结果． (1)假设xp~xI(i,j)是任意一个候选查询结果，由Spring算法可知，SVi,j(m).sp 小于等于epsilon，另有该查询结果对应的DTW路径(即在SVi,p-i+1(1)与SVi,j(m)之间存在的DTW路径Ri,j(m))上所有成员的d值都会小于等于epsilon．因为任何d值大于epsilon的成员都不可能存在于候选查询结果的DTW路径上，所以对于STWM中d值大于epsilon的成员取值计算的省略都不会影响最终的候选查询结果，于是所有的候选查询结果都不会受SMi 中d 值大于epsilon的成员取值计算省略后的影响． (2)由Spring算法可知，当xp~xI(i,j)成为候选查询结果后，之后每个列向量产生后，都需要判别该候选查询结果是否是真正的查询结果．具体方法是对于新列向量中起始位置sp 属于区间[p,I(i,j)]中的成员，如果它们的d值都大于SVi,j(m)的d值SVi,j(m).d，则该候选查询结果为真实查询结果．假设在向量SVi,l  产生后，我们得到结论xp~xI(i,j)是真实查询结果，则有该向量中起始位置在区间[p,I(i,j)]中的成员，其d值都大于SVi,j(m).d.如果这些成员中没有d值大于epsilon的成员，显然，省略掉SMi 中d值大于epsilon的成员取值计算并不会影响最终的判断结果；如果这些成员中有d值大于epsilon的成员，则有这些成员的d值一定大于SVi,j(m).d，所以最终结果取决于这些成员中d值小于等于epsilon的成员，因为这个省略操作并不会省略掉矩阵列向量中d值小于等于epsilon的成员取值，所以不会影响最终判断结果． 综上，定理1成立．                                  证毕． 设FSM算法中的STWM为FM，  Spring算法中的STWM为SM．由Spring与FSM算法可知，前者与后者相比，省略了很多不必要成员取值的计算，而这些省略不会影响矩阵中剩余成员的取值计算，也不会影响最终查询结果．所以在本部分SM中成立的性质，在FSM算法下的FM中同样成立． 2) 关于猜想的分析证明 设SWi，SWi+1是任意2个相邻滑动窗口，FMi与FMi+1是这2个窗口成员在FSM算法下对应的STWM.  由滑动窗口特点可知，SWi 上后|SW|-|EW|个数据流成员和SWi+1上前|SW|-|EW|个数据流成员完全相同．另设FMi 中后|SW|-|EW|个列向量组成的子矩阵为FLMi，前|SW|-|EW|个列向量组成的子矩阵为FFMi．显然FLMi 与FFMi+1分别为由SWi，SWi+1上相同数据流成员在2个矩阵中对应的列向10  计  算  机  学  报  2016年 量组成的矩阵．我们可以通过对SWi 与SWi+1上相同数据流成员重新执行FSM 算法来得到FFMi+1．设Fvi,j 是FLMi 中第j 个列向量，UFvi,j为Fvi,j 所对应的数据流成员在FFMi+1中对应的列向量，显然UFvi,j 是FFMi+1中的第j 个列量，且FFMi+1由所有UFvi,j 组成．同样使用文献[1-2]的查询实例，假设数据流X={11，20，3，6，10，14，15，3，5，1}，查询序列Y={2，6，9，13，15，4}，epsilon=15，SWsize=4，|EW|=2，我们在图6中实例说明了FLMi 与FFMi+1，以及Fvi,j 与UFvi,j 之间的关系．     (a) FM1                                                                                    (b) FM2   图6    FLMi 与FFMi+1示例 在图6的FM中，每个成员包括2部分取值，括号内外分别为起始位置sp与成员d值．图中线虚线区域分别是FM1 与FM2．点虚线区域分别是FLM1与FFM2；其中FLM1是由Fv1,1，Fv1,2，Fv1,3，Fv1,4，Fv1,5，Fv1,6构成；FFM2是由UFv1,1，UFv1,2，UFv1,3，UFv1,4，UFv1,5，UFv1,6 构成．我们通过对Fv1,1，Fv1,2，Fv1,3，Fv1,4，Fv1,5，Fv1,6 所对应的数据流成员执行FSM 算法来得到UFv1,1，UFv1,2，UFv1,3，UFv1,4，UFv1,5，UFv1,6．   考虑FFMi+1的构造过程，对于相邻两个窗口中的相同数据流成员，按照当前使用FSM 算法重新处理完的成员中是否有查询结果产生，可分为有查询结果，和没有查询结果产生2种情况． (1)在当前已被处理完成的数据流成员中没有查询结果产生 为了便于对当前情况下理论依据进行证明，本部分我们会先对Spring算法下相邻窗口的相同数据流成员在这两个窗口STWM中对应列向量成员取值关系进行分析，并以引理形式给出分析结果．接着基于此在定理2中完成对理论依据的证明． 令SMi 与SMi+1分别是2个相邻滑动窗口SWi，SWi+1中成员在Spring算法下对应的STWM．另设SMi 中后|SW|-|EW|个列向量组成的子矩阵为SLMi，前|SW|-|EW|个列向量组成的子矩阵为SFMi．显然SLMi 与SFMi+1分别为由SWi，SWi+1上相同数据流成员在SMi 与SMi+1中对应列向量组成的矩阵．与FSM算法下情况类似，我们可以通过对SWi 与SWi+1上相同数据流成员重新执行Spring算法的来得到SFMi+1．设Svi,j 是SLMi 中的第j 个列向量，而USvi,j为该向量所对应的数据流成员在重新执行Spring算法后得到的新向量，显然USvi,j 是SFMi+1中的第j个列量，且SFMi+1由所有USvi,j 组成． 引理2．在SFMi+1 的构造过程中，如果存在SLMi 中成员Svi,j(t)满足条件Svi,j(t).sp=USvi,j(t).sp，且Svi,j(t).d=USvi,j(t).d(1£t£m)，则对于Svi,j 与USvi,j中索引小于t 的所有成员有如下结论成立：Svi,j(t1).sp=USvi,j(t1).sp，Svi,j(t1).d=USvi,j(t1).d成立，其中t1<t． 证明．设Svi,j(t).sp=p，由引理1的结论1可知，Svi,j(t)在SLMi 中与xp间存在一条唯一DTW路径，我们把该路径命名为R1，因为当满足条件Svi,j(t).sp =USvi,j(t).sp，且Svi,j(t).d=USvi,j(t).d的USvi,j(t)出现时，当前已被处理完成的所有数据流成员中并没有查询结果产生，所以路径R1上的所有成员在当前已得到的SFMi+1中依然存在，我们把此时的这条路径轨迹称为R2，我们只要能证明R2上所有成员的取值与R1都相同，则由Spring算法可知，SFMi+1中位于R2下的成员与SLMi 中位于R1下矩阵成员取值都相同，所以有Svi,j(t1).sp=USvi,j(t1).sp，Svi,j(t1).d= USvi,j(t1).d，(t1<t)成立，也即我们要证明的结论成立． 考虑R1上的成员，由Spring算法可知，每个成员都是其相邻下一个成员的dbest所在成员．又因为R2 上所有成员的位置与其在R1上的对应成员置位置都相同，所以在R2中，如果每个成员仍是其相邻下一个成员的dbest所在成员，结合Spring算法可知，R2与R1上的成员取值完全相同，由前面分析可知，论文在线出版号  No.176  王少鹏等：一种滑动窗口下数据流Disjoint查询的增量处理算法  11 结论成立；如果R2上有成员的dbest成员发生变化，由Spring算法可知，新dbest成员d值一定小于原来的dbest成员d值，R2最后一个成员d值与其在R1中的ｄ值相比也会变小，也就是说此时USvi,j(t)与xp间存在一条路径，该路径的DTW值小于R1的DTW值Svi,j(t).d，所以此时USvi,j(t)的d值不可能与Svi,j(t).d相等，这与条件矛盾，所以这种情况不可能． 总之结论成立．                                            证毕． 定理2．设hi,j 与uhi,j 分别是与向量Fvi,j，UFvi,j对应的highest；而dmini,j 与udmini,j 分别是与向量Fvi,j 和UFvi,j 对应的dmin值，FRi,j 和UFRi,j 分别是与dmini,j 与udmini,j 对应的候选查询结果．在使用FSM 算法重新处理相邻窗口中相同数据流成员获得FFMi+1的过程中，对于FFMi+1中的任意列向量UFvi,j ，如果满足如下条件：(1)  hi,j=uhi,j ；(2) Fvi,j(hi,j).sp=UFvi,j(uhi,j).sp，Fvi,j(hi,j).d=UFvi,j(uhi,j).d；(3) dmini,j＝udmini,j；(4) FRi,j=UFRi,j；则有FFMi+1中剩余列向量成员与FLMi 中位于Fvi,j 之后的对应列向量成员取值都相同，同时在它们构造过程中产生的查询结果相同． 证明．假设在求得FFMi+1成员取值的过程中，UFvi,j-1的highest位置并没有变化．由FSM与Spring算法间的关系，以及引理2可知，条件(1)(2)的成立可以保证Fvi,j 与UFvi,j 中索引值小于hi,j 的成员，其d值与sp值都对应相同．而由FSM算法可知，该算法STWM的每个列向量成员取值只与前一个列向量的highest值，dmin值，与dmin值对应的候选查询结果，以及前一个列向量中索引小于highest的所有成员取值相关，所以再结合条件(3)(4)，可推得FFMi+1中剩余其他列向量成员与FLMi中剩余列向量中对应成员取值相同，产生查询结果也相同． 假设在求得FFMi+1成员取值过程中UFvi,j-1的highest位置发生变化，由FSM算法可知，此时只需对上面情况下FFMi+1 中位于UFvi,j 后(包括UFvi,j)的矩阵成员作相应调整即可，而这个调整也仅与其中d值大于epsilon的成员相关，也即调整后，其中d值小于等于epsilon的成员位置与取值并没有发生变化，由定理1可推得这种情况下FFMi+1中剩余列向量成员与FLMi 中位于Fvi,j 之后对应列向量 成 员 在 构 造 过 程 中 产 生 相 同 查 询 结果．                                                                      证毕．           仍然使用文献[1-2]中的查询实例．假设数据流X={11，20，3，6，10，14，15，3，5，1}，查询序列Ｙ={2，6，9，13，15，4}，epsilon=15，SWsize=4，|EW|=2，图7中(a)(b)的线虚线区域分别给出了相邻2个窗口的FM；2个FM中列向量内具有横线和竖线背景成员的数字分提标出了该向量中highest 与lowest 成员，而它们在向量中的索引分别是该向量中highest与lowest 变量的取值．图7的FM中，每个列向量上面是按照FSM 算法处理完该向量后得到的dmin值．     (a) FM1                                                                         (b) FM2 图7  定理2的说明 定理2告诉我们，在使用FSM算法处理相邻两个窗口中的相同数据流成员的时候，如果存在一个数据流成员在相邻两个窗口的FM中对应的相关信息都分别相同，则有其他相同数据流成员在这２个窗口FM中对应列向量的成员取值，特别是其中d值小于epsilon的成员取值都完全相同．比如图7中的x3在FM1与FM2的列向量中，其highest(这里该值为2)，第highest个成员取值(包括d值与sp值)，dmin取值(这里都为¥)，以及候选查询结果(这里为null)都相同，所以2个窗口中其他相同数据流成员在这两个窗口的FM中对应列向量成员取值完全相同，其中d值小于epsilon的成员取值也完全相同．         (2)在当前已被处理完成的数据流成员中有查询结果产生 12  计  算  机  学  报  2016年 当前情况下分析证明过程与情况1相类似，我们会先对Spring算法下相邻窗口相同数据流成员在这两个窗口STWM中对应列向量成员取值的关系进行分析，并以引理形式给出分析结果．接着在此基础之上在定理3中完成了对理论依据的证明． 引理3．假设USvi,j 构造完后，在当前已被处理完成的数据流成员中有查询结果产生．这时如果有Svi,j(t).sp=USvi,j(t).sp，Svi,j(t).d=USvi,j(t).d(1£t£ m)，则对于这2个向量中索引小于t 所有成员有如下结论成立：Svi,j(t1).sp=USvi,j(t1).sp，Svi,j(t1).d= USvi,j(t1).d成立，其中t1<t． 证明．与引理2证明相类似，设Svi,j(t).sp=p，Svi,j(t)在SLMi 中与xp间的DTW路径为R1．因为当满 足 条 件Svi,j(t).sp=USvi,j(t).sp ，且Svi,j(t).d= USvi,j(t).d的USvi,j(t)出现时，当前已被处理完成的所有数据流成员中有查询结果产生，由Spring算法可知路径R1上的成员在当前已得到的SFMi+1中有2种情况，1)R1上的成员在SFMi+1中依然存在；2)R1上有的成员在SFMi+1中的d值变为¥． 情况1下的引理证明过程与引理2的证明相似，此处不再赘述，易得结论成立． 情况2的出现完全是因为Spring算法中当构建完STWM中的列向量产生查询结果xs~xe时，该列向量中所有sp值小于等于e的成员，其d值都被设为¥，当SFMi+1中R1上存在符合这样情况的成员时，相关成员会因为d值被设为¥而使它们自身不存在于任何路径中．这种情况下，因为有条件Svi,j(t).sp=USvi,j(t).sp，且Svi,j(t).d=USvi,j(t).d成立，所以基于引理1的结论1可知USvi,j(t)在SFMi+1中与xp间存在一条DTW路径，我们将其命名为R2，R2上不存在d值为¥的成员．接下来考虑R2在原来SLMi 中的状态，我们把R2在SLMi 中的路径轨迹称为R3．与前分析类似，R3中成员也有两种情况，1)R3中不存在¥成员；2)R3中存在¥成员．考虑第1种情况，如果R2与R3上每个成员的dbest成员都一样，则R2与R3上每个成员的d值与sp值都相同，结合引理2证明过程可知，结论成立；如果R3上存在某个成员的dbest成员发生变化，由Spring算法可知，新dbest成员d值一定会变小，最终R3的d值也会变小，即有R3的d值小于Svi,j(t).d，也就是说在SLMi 中的Svi,j(t)与xp间存在一条d值小于Svi,j(t).d的路径，所以此时USvi,j(t)的d值不可能与Svi,j(t).d相等，这与条件矛盾，所以这种情况不可能；考虑第2种情况，由前面可知此时R1在SFMi+1中有d值为¥的成员存在，又因为R2上不存在d值为¥的成员，所以R2一定位于R1的下面，对于SLMi 中的R1与R3，因为R3与R2具有相同的路径轨迹，所以R3也一定位于R1的下面．如果此时R3中存在¥成员，由Spring算法可知，R1中一定也存在¥成员，但由条件可知，SLMi 中的R1并不存在¥成员，矛盾，即这种情况不存在．总之在所有可能出现的情况中，都有结论成立．                                    证毕． 定理3．设hi,j 与uhi,j 分别是与向量Fvi,j，UFvi,j对应的highest；而dmini,j 与udmini,j 分别是与向量Fvi,j 和UFvi,j 对应的dmin值，FRi,j 和UFRi,j 分别是与dmini,j，udmini,j对应的候选查询结果．在使用FSM算法重新处理相邻窗口中相同数据流成员获得FFMi+1 的过程中，对于FFMi+1 中任意列向量UFvi,j，如果在其构造完成后已有查询结果产生，同时也有如下条件成立：1)hi,j=uhi,j；2)Fvi,j(hi,j).sp= UFvi,j(uhi,j).sp，Fvi,j(hi,j).d=UFvi,j(uhi,j).d；3)dmini,j＝udmini,j；4)FRi,j=UFRi,j，则可推得FFMi+1中剩余列向量成员与FLMi 中位于Fvi,j 之后的对应列向量成员取值都相同，同时在它们构造过程中所产生查询结果也相同． 证明．定理3证明过程与定理2的证明过程类似，只需将其中的证明依据引理2变为引理3即可．此处不再赘述．                      证毕． 定理3的内容同样可以结合图7来说明．由定理2可知在我们处理相邻窗口上的相同数据流成员时，如果有如下2个条件成立：1)存在一个成员在两个窗口FM中对应列向量的相关信息都相同，2)对于两个窗口中所有已被处理完成的相同数据流成员，如果在处理它们的过程中没有查询结果产生，那么其他相同数据流成员在两个窗口FM中对应的列向量成员取值都相同，且产生的查询结果也相同．比如图7中的x3就是这种情况，由定理2可知，其他相同数据流成员在两个窗口FM中对应列向量的相关信息都相同，而这些列向量在两个矩阵的构建过程中产生的查询结果也一样；定理3的内容是说，如果条件1满足，但是条件2不满足，即对于两个窗口中所有已被处理完成的相同数据流成员，如果在处理它们的过程中有查询结果产生，这种情况下，结论也是成立的．比如x3之前如果已经处理了很多相邻2个窗口中的相同数据流成员，而且在处理的过程中已经有查询结果产生，这时如果出现了满足条件1)的x3，则仍有结论成立． 论文在线出版号  No.176  王少鹏等：一种滑动窗口下数据流Disjoint查询的增量处理算法  13 4.2.3    DQPIC算法 1)DQPIC算法执行步骤 定理2，3从2个角度对于DQPIC算法的理论基础进行了完整地分析与证明．基于这2个定理以及4.2.1 部分的分析，可得到具有增量计算特点的DQ-SW查询处理算法DQPIC．具体执行步骤如下： 首先，在第1个窗口上执行naive算法得到查询结果．在这个过程中保留每个数据流成员在当前窗口FM中对应列向量的相关参数，包括每个列向量的highest，列向量中索引为highest的成员取值(d值，sp值  )，naive算法在处理完该数据流成员后的dmin值，以及与该dmin值对应的候选查询结果，除此之外，该窗口上产生的查询结果，以及窗口中最后一个数据流成员对应的列向量也需要保留． 接着处理下一个窗口上数据流成员．此时分为2个阶段：对于相邻窗口上相同数据流成员进行处理和对新添加基本窗口中的数据流成员进行处理． 在第1个阶段，首先继续用naive算法处理相邻窗口上相同数据流成员．与之前一样需要保留相关参数，同时还需要比较相同数据流成员在两个窗口上参数取值是否相同(定理2，3)．如果有成员满足这个条件，则将剩余相同数据流成员在前一个窗口上相关参数作为它们在当前窗口上相关参数，将剩余相同数据流成员在前一窗口处理过程中产生的查询结果，作为当前窗口上这些成员被处理时产生的查询结果(定理2，3)，它们和当前窗口上已被保留的查询结果构成了所有相同数据流成员在当前窗口上的查询结果；若不存在这样成员，则一直执行naive算法，当处理完所有相同数据流成员后，即得到这部分成员在当前窗口上查询结果；接着处理当前窗口中新加的数据流成员，即进入第2阶段． 在第2阶段，如果第1阶段是以第1种情况结束，由FSM算法可知，该算法STWM每个列向量成员取值只与前一个列向量的highest值，dmin值，与dmin 值对应的候选查询结果，以及前一个列向量中索引小于highest的所有成员取值相关，所以只要知道最后一个相同数据流成员在当前窗口上相关参数，和对应列向量取值即可，而因为此时在前一窗口上保留的最后1个数据流成员对应的列向量和与之相关的参数符合要求，所以只需基于它们对新基本窗口数据流成员执行naive算法即可，当然这个过程也需要保留数据流成员相关参数，和最后1个数据流成员对应的列向量；如果第1阶段是以第2种情况结束时，则继续对新基本窗口中成员执行naive算法即可，这个过程也需要保留数据流成员相关参数和最后1个数据流成员对应的列向量． 最后处理完2个阶段后，由它们上的查询结果共同构成了当前窗口上的完整查询结果． 2)DQPIC算法的具体描述 根据上面的执行步骤，我们在算法1中给出了DQPIC算法的详细描述．为减少因滑动窗口中内容更新而造成的资源损耗，我们采用可重写循环滑动窗口思想[22]存放新来的基本窗口成员． 算法1．DQPIC. 输入：数据流X，查询序列Y，滑动窗口大小SWsize，基本窗口宽度|EW|，相似阈值epsilon； 输出：满足相似性条件的DQ-SW查询的结果． 1．数据流X不断进行 2．{ 3．  新基本窗口EWi+SWsize-1到达时，最近SWsize个基本窗口组成流上滑动窗口SWcur;   4．  [Paracur,resultcur]=Preserve_FSM(SWcur); //对当前窗口成员执行FSM算法，保留相关信息 5．  Report(resultcur); //输出当前窗口结果;   6．  winelenum=SWsize; 7．  WHILE EWi+SWsize arrives  8．  { winelenum++,result1tem=null; 9．      SW[(winelenum-1)%|SWsize|]¬EWi+SWsize; //使用循环滑动窗口存放新到来的EWi+SWsize 10．  T=(i+1); 11．    BEGIN from EWT，FOR(each EW in SWcur) 12．  { IF(EW!=EWi+SWsize)   13．    { FOR(each element v in the EW ) 14．        { [tempara, resulttem]=Preserve_FSM(v);   15．          result1tem=result1temÈresulttem; 16．        IF((tempara(dmin,sp,candidate,hbound,Vhbound)=Paracur,v(dmin,sp,candidate,hbound,Vhbound)) 17．            {[Paracur((winelenum-1)%|SWsize|),resulttem]¬   Preserve_FSM_P(EWi+SWsize,Paracur.lastvec); 18．      resultcur=result1temÈresulttemÈgetresult( resultcur); 19．              BREAK; 20．            } 21．            ELSE 22．              Update Paracur,v with tempara; 23．          }//FOR 24．        }//IF 25．        ELSE 14  计  算  机  学  报  2016年 26．        {[Paracur((winelenum-1)%|SWsize|),resulttem]¬                Preserve_FSM_P(EWi+SWsize,Paracur.lastvec); 27．    resultcur=result1temÈresulttem;   28．          }   29．      }//BEGIN 30．      Report(resultcur);         31．      i++,  并转到第7行; 32．  }//WHILE 33．} 设FMcur与FMnext分别是FSM算法在当前窗口与相邻下一个窗口上的STWM，而FLMcur 与FFMnext分别是它们中对应的LSM与FSM． 算法执行时首先对第1个窗口上数据流成员执行FSM算法，并保留它们在FMcur中对应列向量的参数，这些参数有每个列向量的curbound.highest(用hbound表示)，该列向量中索引为hbound的成员取值Vhbound，sp值以及与该向量相关的dmin值，与dmin对应的候选查询结果candidate．除此之外，FLMcur中的最后1个列向量，还有窗口上STWM构造过程中产生的查询结果，都需要保留．当窗口中成员处理完成后，输出该窗口上结果(行4~5)； 当新数据到来后，更新窗口并处理新窗口成员(行7~11)；对相邻窗口中相同数据流成员执行FSM算法，保留相关参数信息，并将结果放入result1tem 集合(行14~15)，这个过程也是FFMnext的构造过程，需要同时比较相同数据流成员在FLMcur与FFMnext对应列向量中索引为hbound 的成员参数取值是否相同(行16)．若相同，则无需处理其他相同数据流成员，直接将这些成员在前一窗口上相关信息作为它们在新窗口中相关信息保留．在FLMcur中最后1个列向量及其相关参数基础上，对新基本窗口中成员执行FSM算法，并保留结果到集合resulttem 中(行17)．此时resultcur中存放的是前一窗口上查询结果，得到前一个窗口上在处理当前成员之后所有成员时所产生的查询结果，则该结果与result1tem 和resulttem 并集即为当前窗口上查询结果(行18)．如果不相同，使用相同方法继续处理剩余相同数据流成员(行21~22)．如果在处理相邻窗口相同数据流成员过程中没有任何成员在FLMcur与FFMnext中对应参数完全相同，那么此时执行过程与naive  算法相同，考虑到窗口成员处理的完整性，假设处理完最后1个基本窗口得到的查询结果集合为resulttem，则此时result1temÈresulttem 即为当前窗口上查询结果(行25~30)，新窗口上查询结果求解过程结束． 4.2.4  关于DQPIC算法时间和空间复杂度的分析 1) 时间复杂度 由前面分析可知，DQPIC算法使用naive算法求得数据流上第一个窗口上的DQ-SW查询结果；对于其他窗口上的查询结果，该算法可基于前一窗口上的查询结果增量获得．设数据流成员个数为N，则所有窗口数为(N/|EW|)-SWsize+1，算法在第1个窗口上时间复杂度为O(SWsize´|EW|´|Y|)；其他每个窗口上的时间复杂度由2部分组成：处理相邻窗口上重叠成员部分，和处理当前窗口相对于前一窗口新增基本窗口中成员所花时间开销部分．假设对第1部分成员的平均处理个数为T，在前一个窗口查询结果集合中搜索当前窗口上查询结果需要遍历的平均成员个数为P，则其他每个窗口时间开销为O(|Y|´T+P+|EW|´|Y|)．设M=(N/|EW|)-SWsize+1，则平均每个窗口时间复杂度为[O(SWsize´|EW|´|Y|) +O((M-1)´(|Y|´T+P+|EW|´|Y|))]/M，即O(SWsize´ |EW|´|Y|)/M+O(|Y|´T+P+ |EW|´|Y|)．当相邻2个窗口重叠部分成员在2个窗口的STWM中对应信息都不相同时，有T=(SWsize-1)´|EW|，同时此刻也无需使用前一个窗口的查询结果，即P=null，DQPIC算法退化为naive算法，由FSM算法可知，此时每个窗口上的最坏情况下的时间复杂度为O(SWsize´|EW|´|Y|)． 2) 空间复杂度 DQPIC算法需要保留每个窗口上数据流成员，同时也需要2个大小为|Y|的列向量来完成当前窗口每个成员相关信息的获得；除此之外还需要额外空间存放与每个窗口成员相关的信息，因为窗口成员所占有的空间开销是O(SWsize´|EW|)，所以这部分额 外 空 间 所 占 有 的 空 间 开 销 为O(M1´SWsize´|EW|)，其中M1>1．另外DQPIC算法需要保留当前窗口上最后一个数据流成员在FM中的对应列向量，再加上当前窗口查询结果的空间开销Q，所以当前窗口上的空间总开销为O(3|Y|+M1´SWsize´|EW|+Q)；比较起来naive 算法主要空间开销在于每个窗口上的数据流成员，和2个大小为|Y|的列向量，除此之外并不需要保留其他多余信息，所以空间开销为O(2|Y|+SWsize´|EW|)． 5  实验及结果分析 本部分的实验有2个目的：1) DQPIC算法有效性的验证，即实例证明DQPIC算法与naive 算法的论文在线出版号  No.176  王少鹏等：一种滑动窗口下数据流Disjoint查询的增量处理算法  15 执行结果是相同的；2)与现有的精确Disjoint查询处理算法进行对比，评价DQPIC算法的性能方面的优劣． 5.1    实验环境及数据样本 本文实验中的算法都用C语言实现，运行在虚拟机的Linux环境中．电脑配置是Intel(R) core(TM) i5  CPU  650  @3.20GHz  CPU，虚拟机的版本是vmware5.5.3 ， 虚 拟 机 上Linux 使 用 的 是redhat2.4.20．实验分别使用真实和人工合成数据验证算法性能．具体来说真实数据使用了SST，人工合成数据使用了[1]中的Maskedchirp．SST是太平洋海洋环境实验室测定的海面温度变化序列，共61437个观测数据，每个数据元组有4个属性，本部分实验中只用温度属性；Maskedchirp 是由含有白噪声的不连续正弦波组成，其中任何2个不连续正弦波的周期都不相同，整个形式与真实的声音数据相类似，共有20000个数据点．实验中查询序列通过抽取数据样本中任意长度序列得到，而与Maskedchirp相关的查询序列在文献[1]中可获得．为了简化实验，我们使用了文献[1-2]以及文献[9,16,22]中数据流模似方式，即将样本读入内存，然后顺序访问每个数据，从而模拟数据流场景．所有数据都是1维，实验执行10次，结果取平均值． 5.2  DQPIC算法的有效性 本部分实验中，因为查询结果数目较大，为了便于分析，这里定义了DQPIC算法相对于naive算法的查全率与查准率，我们分别用Rrecall与Rprecision表示．设SDresult与SNresult分别为相同参数设置下，DQPIC和naive 算法的执行结果集合，|SDresult|与|SNresult|分别是这2个集合中成员数目，令Vequal表示两个集合中相等查询结果的个数．这里定义SDresult中的任一查询结果A与SNresult中的查询结果B，如果它们对应的窗口具有相同起始位置，且A与B也相同，则认为A与B相等；如果2者中有1项不同，则A与B不相等．这样Rrecall与Rprecision可表示为： Rrecall= Vequal/|SNresult|         (6) Rprecision=Vequal/|SDresult|.          (7) 显然如果DQPIC算法Rrecall与Rprecision都为1，则说明DQPIC与naive  算法在每个窗口上执行结果相同．实验参数设置与执行结果如表2所示．(其中标出的2行也是性能评价实验中的参数取值)表2    实验1中的相关参数设置及DQPIC算法的Rrecall与Rprecision   数据样本  样本大小  SWsize  |EW|  dimension  epsilon  |Y|  Rrecall  Rprecision SST  61437  25  200  1  1000  3000  1  1 SST  61437  30  200  1  1500  3000  1  1 SST SST 61437 61437 35 40 200 200 1 1 2000 2500 3000 3000 1 1 1 1 Maskedchirp  20000  20  200  1  100  2048  1  1 Maskedchirp  20000  25  200  1  200  2048  1  1 Maskedchirp Maskedchirp 20000 20000 30 35 200 200 1 1 300 400 2048 2048 1 1 1 1 由表2 可见在这些数据样本及相关参数设置下，DQPIC算法查准率与查全率值都是1，即DQPIC与naive算法结果相同，也即在1维数据中，DQPIC算法能准确得到数据流上DQ-SW查询结果． 5.3  DQPIC算法的性能评价 就现有研究来看能用于解决DQ-SW查询的研究并不多．通过分析发现将文献[3]中算法用于每个滑动窗口可得到解决本文问题的算法，称为EBW(eHaarSubseq  based  on  window)算法；文献[9]中FSDQ算法与本文要解决问题相同．它们与naive算法一起将作为DQPIC算法性能评价的对比算法．   5.3.1  DQPIC算法运行时间分析 本部分实验使用了SST与Maksedchirp样本，具体实验分析如下： 首先分析SWsize 对算法执行时间的影响．实验中参数取值见表2，实验结果如图8所示． 16  计  算  机  学  报  2016年  (a) Maskedchirp                                            (b) SST 图8    算法在SWsize发生变化时的执行时间对比 由图8中不同样本下几种算法的执行时间比较可以看出，几种算法的执行时间随SWsize的增加单调递增．这主要因为窗口越大，需要处理的数据流成员就越多，对于DQPIC算法，由4.2.4的分析可知，在该算法的时间开销中，O(SWsize´|EW|´|Y|)/M与O(|Y|´T+P+|EW|´|Y|)部分都会因为SWsize大小的增加而变大，所以算法的时间开销会增大，而图中DQPIC算法时间所呈现出的变化状态，也印证了这一点．另外由图中还可以看到，EBW算法执行时间最多，这是因为在当前参数下，查询序列成员取值基本涵盖了窗口中所有数据流成员的取值的最大与最小值，这使得EBW算法对于数据流中与查询序列不相似的序列的剪枝能力减弱，这样基本需要对大部分数据流成员执行Spring算法，所以执行时间较大；naive算法执行时间小于FSDQ算法，这是因为虽然FSDQ算法使作了边界路径技术，但该算法对于创建元素之前的成员都使用Spring算法来处理，另外该算法也忽略了在使用Spring算法处理相邻两个窗口中位于创建元素之前相同数据流成员时存在的冗余运算，所以时间开销较大；另外由图中可以看出DQPIC算法时间开销最小，这也证明了DQPIC算法相对于其他算法的时间优势，说明了该算法的时间有效性． 分析相似阈值epsilon 对于算法执行效果的影响．实验中参数取值见表2，实验结果如图9所示．  (a) Maskedchirp                                             (b) SST   图9    算法在epsilon发生变化时的执行时间对比 由图9可以看出EBW，naive，DQPIC3种算法的执行时间随epsilon 取值的增加而单调增加，而FSDQ算法的执行时间随epsilon取值的增加单调减少．对于EBW算法，因为该算法具体仍然是用Spring算法来执行相似性查询的具体处理工作，当epsilon较小时，在构建窗口上STWM的过程中，多数列向量最后一个成员d值不小于epsilon，所以不需要进一步判断该成员所在DTW路径对应的数据流序列是否是查询结果；随着epsilon的增加，满足该条件的成员越来越多，相应地也增加了很多判别操作，执行时间增加；对于naive算法，因为epsilon的增加，会使得在确定窗口上STWM中所有向量lowestbound和highestbound的时候，计算更多成员值，所以执行时间增加；FSDQ算法中，epsilon的论文在线出版号  No.176  王少鹏等：一种滑动窗口下数据流Disjoint查询的增量处理算法  17 增加产生更多DQ-SW查询结果不为空的窗口，所以更多窗口上的FSDQ算法是利用边界路径来减少窗口上naive算法中存在的冗余运算，而由FSDQ算法可知，对于一个确定窗口，基于边界路径所导致的后一个窗口上naive算法运行时间的减小量大于等于基于伪边界路径所导致的后一个窗口上naive算法运行时间的减少量，所以FSDQ算法执行时间会减少．对于DQPIC算法，考虑对于相邻2个窗口相同数据流成员的处理，如果epsilon取值的增加并没有改变该值变化前数据流中满足定理2，3的成员位置，显然在此时4.2.4部分关于时间开销的分析中，T部分的开销不会变化，如果epsilon取值的增加使该值变化前数据流中满足定理2，3中判别条件的成员位置发生了变化，则需要在之后的相同数据流成员中继续寻找这样的成员，显然此时，T的开销会增加，也就是说随着epsilon取值的增加，T部分的开销会单调增加，另外在使用naive算法处理相同数据流成员的过程中，时间开销也会增加，所以总体来看，时间开销会增加． 分析查询序列长度|Y|对于算法执行效果的影响，实验中参数取值见表2，实验结果如图10所示．  (a) Maskedchirp                                             (b) SST   图10    算法在查询序列长度发生变化时的执行时间对比 由图10 可以看到，几种算法的执行时间都会随着查询序列长度的增加而单调增加．这是因为查询序列长度的增加，会使每个窗口上构建的STWM中行数增加，所以多出了很多相关的计算量；另外由图中我们也可以看到EBW算法的时间增长较快，这是因为该算法中所使用的Spring算法需要对STWM中每个新增加的成员进行处理；naive  算法的执行时间增加渐慢，因为对于Maskedchirp样本的实验，当查询序列长度在400~1600间变化时，STWM中的多数列向量的highestbound 都在变化(SST实验中Y的长度在200~2700间变化，情况相同)，而由FSM算法可知，随着|Y|的增加，STWM中列向量highestbound的位置只会上升，不会下降，所以基于FSM算法可推得，此时naive的算法时间增加较明显；而当|Y|取值继续增加时，STWM中列向量的highestbound多数没有发生变化，所以此时naive 算法的执行时间增加较为平缓；对于FSDQ算法，在查询序列相对较小时，所有窗口中能产生查询结果的较多，该算法在这些窗口上会基于边界路径来减少窗口上Spring算法中存在的冗余运算，而随着查询序列的增加，产生查询结果的窗口变少，该算法会在不产生查询结果的窗口上基于伪边界路径技术来减少窗口上Spring算法中存在的冗余运算．因为FSDQ算法中使用边界路径技术比使用伪边界路径技术能更好地消除naive算法中的冗余运算，所以随着查询序列长度增加，FSDQ算法对冗余运算的消除效果变差，算法时间增加变快；由图中还可以看到DQPIC算法执行时间最小，且随查询序列长度的增加而增加，我们可以结合4.2.4部分时 间 开 销 来 分 析 ， 因 为4.2.4 中O(SWsize´|EW|´|Y|)/M部分会增加，而O(|Y|´T+P+ |EW|´|Y|)部分也会因查询序列|Y|的增加而增加，所以总体时间开销会增加，另外由图中也可以看到DQPIC算法的时间明显小于其他算法，这也说明了这种算法相对于其他算法的时间优势． 分析单元窗口大小|EW|对于算法执行时间的影响．实验中参数取值见表2，结果如图11所示． 18  计  算  机  学  报  2016年  (a) Maskedchirp                                           (b) SST   图11    算法在|EW|发生变化时的执行时间对比 由图11可知，随着基本窗口大小|EW|的增加，几种算法时间都呈单调增加趋势．这是因为在窗口大小不变的情况下，基本窗口越大，窗口中数据流成员就越多，算法在处理这些数据流成员的时候所需的时间也就越多．EBW算法中的Spring算法因为需要处理窗口STWM中每个成员，所以算法时间增加较快；FSDQ与naive算法分别因为边界路径技术以及边界技术的使用，导致算法时间增加较慢；结合4.2.4部分关于DQPIC算法时间开销的分析可知，当|EW|增加时，O(SWsize´|EW|´|Y|)/M部分会增加，而O(|Y|´T+P+|EW|´|Y|)中的P和T都会随|EW|大小的增加而增加，所以总体来看DQPIC算法时间开销会增加，这一点由图中DQPIC算法时间呈现出的变化态势得以印证，另外也可以看到DQPIC算法时间增加最为平缓，同时在几种算法中时期开销也最小，这也证明了DQPIC算法相对于其他算法的时间有效性． 分析样本大小N对于算法执行时间的影响．实验中参数取值见表2，结果如图12所示．  (a) Maskedchirp                                            (b) SST   图12    算法在样本大小N发生变化时的执行时间对比 由图12可知，随着样本大小N的增加，EBW以及naive 算法的执行时间并不会发生变化；而FSDQ 与DQPIC算法的执行时间都会变小．对于EBW和naive算法来说，它们在每个窗口上的执行时间在epsilon取值不变的时候，只与窗口大小与查询序列长度相关，而这两个方面并不会随着样本大小的增加而发生变化，所以时间开销保持不变；对于FSDQ算法，因为在N较小时(Maskedchirp中N为4000时，或SST中N为10000时)，此时窗口数较少，而且由FSDQ可知，该窗口会使用Spring算法来处理第一个窗口，该窗口的时间效应没有被其他窗口削减太多，所以与EWB算法较为接近，而随着数据样本的增大，窗口数会越来越多，再加上边界界标窗口技术的作用，平均每个窗口上的执行时间会渐渐减少；同样对于DQPIC算法，因为在N较小时(Maskedchirp中N为4000时，或SST中N为10000时)，此时此时窗口数较少，第一个窗口上执行情况与naive算法相同，都是使用FSM算法来处理，与FSDQ算法一样，DQPIC算法与naive算法时间较为接近．随着样本大小增加，窗口个数也会增加，O(SWsize´|EW|´|Y|)/M部分时间开销会减少，而因为O(|Y|´T+P+|EW|´|Y|)部分随样本大小论文在线出版号  No.176  王少鹏等：一种滑动窗口下数据流Disjoint查询的增量处理算法  19 增加，并无太大变化，所以总体时间开销会减少．       5.3.2  DQPIC算法空间开销分析 首先分析SWsize 对算法空间开销的影响．实验参数取值见表2，实验结果如图13所示．  (a) Maskedchirp                                           (b) SST   图13    算法分别在SWsize发生变化时的空间开销对比 由图13可见不同样本下几种算法空间开销都随窗口大小的增加而增加．这是因为窗口越大，需要开辟出存放窗口成员的空间就越大；FSDQ算法因为需要保护现场，保留当前窗口上的查询结果和边界路径(伪边界路径)，所以比naive算法需要更多的空间开销；EBW算法除了保留当前窗口上的数据流成员和查询序列外，还需要保留当前窗口上可能含有查询结果的成员序列，而因为在当前参数下，整个窗口中大部分序列都含有查询结果，所以窗口中大部分成员都被保留下来，这也是EBW算法空间开销多于naive算法的原因；由图中还可以看到随着SWsize的增加，EBW算法空间开销渐渐多于FSDQ算法，这是因为EBW算法中被保留下来的窗口序列会随窗口大小的增加而增加，而相对来说，FSDQ算法空间开销部分在这个过程中只有当前窗口上的查询结果会发生变化，但这个变化幅度并不大；DQPIC算法与FSDQ算法相比，虽然不用保留边界路径(伪边界路径)，但却需要更多空间来存放每个窗口STWM中所有列向量最后一个成员的相关参数值，所以空间开销更大． 接着分析epsilon对算法空间开销的影响．实验参数取值见表2，实验结果如图14所示．  (a) Maskedchirp                                          (b) SST   图14  算法在epsilon发生变化时的空间开销对比 由图14可见，naive算法空间开销在epsilon取值增加的过程中保持不变，这是因为naive算法只保留每个窗口上数据流成员，查询序列，以及STWM 中当前列向量与前一个列向量的lowestbound 和highestbound，而这些空间开销与epsilon取值都不相关；与naive算法相比，EBW算法需要额外空间存放当前窗口上可能含有查询结果的成员序列，所以空间开销多于naive算法；另外由图中可见EBW算法空间开销在epsilon取值增加的过程中基本保持不变，这是因为在当前参数下，窗口上几乎全部成员都含有候选查询结果，所以在epsilon取值增加的过程中，并不会有更多含有候选查询结果的序列被保留；由图14还可以看到，DQPIC算法与FSDQ算法的空间开销随着epsilon20  计  算  机  学  报  2016年 取值的增加而增加，这是因为这两种算法都需要保留每个窗口上DQ-SW查询的结果．而随着epsilon取值的增加，每个窗口上的查询结果逐渐增加，所以这两种算法的空间开销也相应增加．图中FSDQ算法相对于EBW 算法空间开销的减少幅度随epsilon取值的增加渐渐变小，直至反超，这也是因为随着epsilon取值的变大，每个窗口上的查询结果都会逐渐增加． 分析|Y|对于算法空间开销的影响．实验中参数取值见表2，实验结果如图15所示．  (a) Maskedchirp                                             (b) SST   图15    算法在|Y|发生变化时的空间开销对比 由图15 可见几种算法的空间开销随|Y|的增加而增加．这是因为|Y|越大，总会使系统中存放它们的空间变大，所以会有这样的效果．对于FSDQ与DQPIC算法，因为它们相对于naive算法需要保存更多信息，所以空间开销多于naive算法．另外对于FSDQ与DQPIC算法，因为DQPIC相对于FSDQ算法还需要保留每个窗口STWM所有列向量索引为与之相关hbound 的成员的相关参数，以及这些向量被处理后可能产生的查询结果，所以DQPIC算法的空间开销大于FSDQ 算法．EBW相对于FSDQ算法空间开销的增加幅度会先增加后减少，这是因为在开始的时候，随着|Y|的增加，EBW算法需要保留窗口中的候选查询结果序列会越来越多，当|Y|的增加使得整个窗口序列中成员都含有候选查询结果序列时，这时|Y|继续增加对算法空间开销的影响仅限于查询序列的存放；而随着查询序列长度的增加，FSDQ算法的空间开销不仅有查询序列的存放，还有“保护现场”需要保留的当前窗口的最后一个成员在当前STWM中对应的列向量，所以应该是查询序列的2 倍，所以随着|Y|的增加，FSDQ算法的空间开销增加幅度会越来越大，相对于EBW算法空间开销的差距也会越来越小． 分析|EW|对于算法空间开销的影响．实验中参数取值见表2，实验结果如图16所示．  (a) Maskedchirp                                            (b) SST   图16  算法在|EW|发生变化时的空间开销对比 由图16可见，几种算法空间开销在|EW|取值增加的过程中严格单调增加．这是因为|EW|值越大，则窗口中存放的数据流成员就越多，系统为了存放它们也就需要开辟更多的空间．因为FSDQ算法相对于naive算法多出了保留当前窗口上查询结果，边界路径(伪边界路径)以及“保护现场”的空间开销，所以FSDQ算法的空间开销多于naive算法；由图中还可以看到随着|EW|的增加，EBW算法的论文在线出版号  No.176  王少鹏等：一种滑动窗口下数据流Disjoint查询的增量处理算法  21 空间开销渐渐多于FSDQ算法，这是因为EBW算法中被保留下来的窗口序列会随窗口成员的增加而增加，而相对来说，FSDQ算法的空间开销部分在这个过程中只有当前窗口上的查询结果会发生变化，但这个变化幅度并不太大；DQPIC算法相对于FSDQ算法不需要保留边界路径(伪边界路径)，但却需要额外空间保留当前窗口上STWM中索引为与之相关hbound 的成员的相关参数，以及这些向量被处理后可能产生的查询结果，所以DQPIC算法的空间开销大于FSDQ算法． 分析样本大小N对于算法空间开销的影响，实验中参数取值见表2，实验结果如图17所示．  (a) Maskedchirp                                          (b) SST   图17  算法在N发生变化时的空间开销对比 由图17可见，几种算法空间开销随N的增加，变化幅度并不大．对于naive算法，N的增加不会影响到每个窗口上的查询序列长度与窗口中的成员个数；对于EBW算法，因为当前参数下窗口所有成员中都含有候选查询结果序列，所以数据样本大小的增加并不会影响到算法的空间开销；对于FSDQ与DQPIC算法，因为查询结果所占空间相对于其他空间开销部分较小，所以它们的空间开销主要决定于每个窗口上数据流成员个数，查询序列长度，以及相关参数．而这几部分在N增加的过程中并没有太大变化，所以空间开销也有这样的表现． 5.3.3  DQPIC算法的时间与空间开销对比分析 设Atpara，i,与Btpara，i,分别是参数para取第i 个样本点时，算法DQPIC与其他算法执行时间，于是我们可以把DQPIC算法相对于其他算法在para取值变化时的时间平均减少率(average  rate  about the decrement of time，ARDT )定义为：                                         , , ,1(| | / ) /npara i para i para iiARDT At Bt Bt n=æö =-ç÷ èøå            (8) 同理，设Aspara，i,与Bspara，i,分别是参数para取第i 个样本点的时候，DQPIC算法与其他算法的空间消耗，则DQPIC算法相对于其他算法在para取值变化时的空间平均增加率(average  rate  about  the increment of space，ARIS )可定义为： , , ,1(| | / ) /npara i para i para iiARIS As Bs Bs n=æö =-ç÷ èøå            (9) 使用公式(8)和(9)对实验数据进行处理，可以得到DQPIC算法相对于其他算法在不同参数下的ARDT 与ARIS，这里我们用ARISalgorithma 和ARDTalgorithma 分别表示，DQPIC算法相对于算法algorithma的ARIS与ARDT,具体结果如表3所示． 表3    DQPIC算法相对于其他算法在不同参数下的ARDT与ARIS 数据样本  参数  ARISnaive  ARDTnaive  ARISFSDQ  ARDTFSDQ  ARISEBW  ARDTEBW   SWsize  2.12  0.90  1.35  0.93  1.33  0.96   epsilon  2.76  0.92  1.59  0.92  1.57  0.95 Maskedchirp  |Y|  3.27  0.92  2.09  0.88  1.79  0.94   |EW|  1.96  0.84  1.19  0.91  1.22  0.94   N  2.63  0.60  1.74  0.81  1.48  0.84   SWsize  1.69  0.87  1.12  0.91  1.07  0.94 22  计  算  机  学  报  2016年   epsilon  2.41  0.89  1.57  0.90  1.41  0.94 SST  |Y|  3.01  0.90  2.10  0.85  1.69  0.94   |EW|  1.92  0.91  1.27  0.93  1.17  0.94   N  2.39  0.78  1.59  0.83  1.39  0.89 由表3不同参数下，基于Maskedchirp与SST样本的实验结果可以看到，DQPIC相对于naive算法能以增加1.69~3.27 倍的空间开销，换来高达60%~92%的时间减少幅度，换句话说能够实现2.5~12.5倍时间效率的提高；DQPIC相对于FSDQ算法能以增加1.12~2.1 倍的空间开销，实现5.26~14.2倍时间效率的提高；DQPIC算法相对于EBW算法，能以1.17~1.79倍的空间开销的增加，实现6.26~25倍时间效率的提高．通过对DQPIC算法在不同参数下的时间与空间性能变化范围取最大，最小值可得DQPIC算法增加了空间开销1.12~3.27倍，但却因此而换得了算法在执行时间效率上  2.5~25倍的提高．具体来说，DQPIC算法时间在窗口大小增加过程中平均时间效率提高幅度可达25倍之多，这是因为窗口越大，DQPIC算法能省略的冗余运算就越多，这点也可由4.2.4部分时间复杂度的分析与5.3.1实验1的分析可知；而DQPIC算法时间在样本大小增加过程中平均时间效率提高为2.5倍，这是因为DQPIC算法能减少的冗余运算量会随着样本大小的增加而变得越来越多，因为在我们实验中样本大小的变化幅度不太大，所以时间效率的提升幅度也并不太大． 总之，由上面仿真实验可以得出：1) DQPIC算法与naive  算法执行结果相同，能够完整而准确地得到数据流DQ-SW查询的结果；2) 相比于现有其他算法，DQPIC算法增加了空间开销(1.12~3.27倍)，但却因此换得了算法在执行时间效率上大幅度提高(2.5~25倍)．总体来看，DQPIC算法是一种处理数据流DQ-SW查询的有效方法，在对时间效率更重视的应用场景，相对于其他算法有时间优势，特别是在窗口较大的无限数据流DQ-SW查询应用场景中，算法时间优势最好． 6  总结及展望 本文对滑动窗口下不具有全局约束机制的数据流精确Disjoint查询处理问题进行了深入地研究．首先提出了DQ-SW查询的概念；接着针对该查询提出了一种增量处理算法DQPIC，该算法可以减少naive  算法执行过程中因为不具有增量计算的特点而产生的冗余运算；最后通过对公用数据样本的实验证明了该算法的有效性．接下来的研究会从如下几个方向入手：1)继续改进DQPIC算法，主要目的是减少该算法的空间开销；  2)对于全局约束机制下DQ-SW查询的处理问题展开研究，分析基于DQPIC算法思想处理这类查询问题的可行性和相关条件；3)将该算法扩展到多维数据流环境中，验证算法在多维数据流环境下的有效性． 参 考 文 献 [1]    Sakurai Y, Faloutsos C, Yamamuro M. Stream monitoring under the time  warping  distance//Proceedings  of  the  23rd  International Conference on Data Engineering. Istanbul,Turkey, 2007:1046-1055 [2]    Zou  P,  Su  L,  Jia  Y.  Fast similarity matching  on data  stream  with noise//Proceedings  of  the  24th  International  Conference  on  Data Engineering. Cancun, Mexico, 2008: 194-199  [3]    Kashyap S, Lee M-L, Hsu W. Similarity subsequence search in time series  databases//Proceedings  of  the  2011  International  Conference on  Database  and  Expert  Systems  Apllications.  Toulouse,  French, 2011: 232-246 [4]    Niennattrakul  V,  Wanichsan  D,  Ratanamahatana  C-A.  Accurate subsequence matching on data stream under time warping distance// Proceedings  of  the  Advances  in  Knowledge  Discovery  and  Data Mining. Bangkok, Thailand, 2009:752-755 [5]    Rodpongpun  S,  Niennattrakul  V,  Ratanamahatana  C-A.  Efficient subsequence  search  on streaming  data  based  on  time  warping distance.  ECTU  Transactions  on  Computer  and  Information Technology, 2011, 5(1): 2-8 [6]    Wang  Z-L,  Huang  H-T,  Wang  L-J.  Accelerating subsequence similarity  search based  on dynamic time  warping distance  with FPGA//Proceedings  of  the  2013  ACM/SIGDA  International Symposium on  Field  Programmable  Gate  Arrays.  Monterey, USA, 2013: 53-62 [7]    Athitsos  V,  Papapetrou  P,  Potamias  M.  Approximate  embedding- based subsequence matching of time series//Proceedings of the ACM SIGMOD International  Conference  on  Management  of Data.  New York, USA, 2008: 365-378 [8]    Zhou  X-Z,  Li  S-P,  Yan Z,  et  al.  A  narrowest  parallel  line  based approach for data stream similarity detection. International Journal of Advancements in Computing Technology, 2012, 4(8):145-154 [9]    Wang  Shao-Peng,  Wen  Yin-You,  Li  Zhi,  et  al.  A  fast  processing algorithm  on  section disjoint  query  of  data  stream.  Journal  of 论文在线出版号  No.176  王少鹏等：一种滑动窗口下数据流Disjoint查询的增量处理算法  23 Computer Research  and Development,  2014, 51(5):  1136-1148(in Chinese) (王少鹏,  闻英友,  李志等.  一种关于数据流区间Disjoint查询的快速处理算法.  计算机研究与发展, 2014, 51(5): 1136-1148) [10]    Gong  X-Y,  Si  Y-W,  Fong  S-M,  et  al.  NSPRING:  normalization -supported  SPRING  for  subsequence  matching  on  time  series streams//Proceedings  of  the  15th  IEEE International  Symposium  on Computational  Intelligence  and  Informatics.  Budapest,  Hungary, 2014: 373-378 [11]    Ding H, Trajcevski G, Scheuermann P, et al. Querying and mining of time  series  data:  experimental  comparison  of  representations  and distance measures. The VLDB Endowment, 2008, 1(2):1542-1552.  [12]    Rakthanmanon T, Campana B, Mueen A, et al. Searching and mining trillions  of  time  series  subsequences  under  dynamic  time  warping// Proceedings of  the  ACM  SIGKDD  International  Conference  on Knowledge  Discovery  and  Data Mining.  Beijing,  China,  2012: 262-270 [13]    Rakthanmanon T, Campana B, Mueen A, et al. Addressing big data time  series:  mining  trillions  of  time  series  subseuqneces  under dynamic time warping. ACM Transactions on Knowledge Discovery from Data, 2013, 7(3):10-40 [14]    Huang  S-T,  Dai  G-H,  Sun  Y-L,  et  al.  DTW-based  subsequence similarity  search  on  AMD  heterogeneous  computing  plateform// Proceedings  of the 2013  IEEE  International  Confernece  on  High Performance  Computing  and  Communications.  Zhangjiajie,  China, 2013: 1054-1063 [15]    Hundt  C,  Schmidt  S-E.  CUDA-Accelerated  alignment  of subsequences  in  streamed  time  series  data//Proceedings  of  the  2014 Internaltional Conference on Parallel Processing. Minneapolis, USA, 2014:10-19 [16]    Wu Feng, Zhong Yan, Wu Qing-yuan, et al. Similarity search in data stream  with  adaptive  segmental  approximations.  Chinese  Journal  of Software, 2009, 20(10):2867-2884(in Chinese) (吴枫，仲妍，吴清源等.  基于适应性分段估计的数据流相似性搜索.  软件学报, 2009,20(10): 2867-2884) [17]    Zhou M, Wong M-H. Efficient online subsequence searching in data streams  under  dynamic  time  warping distance//Proceedings  of  the 24th International Conference on Data Engineering. Cancun, Mexico, 2008: 686-694 [18]    Bui C-G, Duong T-A. Similarity search in multiple high speed time series  streams under  dynamic time  warping//Proceedings  of  the 2nd National  Foundation  for Science  and  Technology  Development Conference on Information and Computer Science. Ho Chi Minh city, Vietnam, 2015:82-87 [19]    Papadopoulos  S,  Cormode  G,  Deligiannakis  A, et  al.  Lightweight authentication  of  linear  algebraic  queries  on  data  streams// Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data. New York, USA, 2013: 881-892 [20]    Papadopoulos  S,  Cormode  G,  Deligiannakis  A, et  al.  Lightweight query  authentication  on  streams.  ACM  Transactions  on  Database Systems, 2014, 39(4): 30-75 [21]    Herbst  S,  Pollner  N,  Tenschert  J, et  al.  An  alggebra  for  pattern matching, time-aware  aggregates  and  partitions  on  relational  data streams//Proceedings  of  the  9th  ACM  International  Conference  on Distributed Event-Based Systems. Oslo, Norway, 2015: 140-149 [22]    Li  Jun-Kui,  Wang  Yuan-Zhen.  Rewritable circular sliding window: Towards effective on-line data stream.  Chinese Computer  Science, 2007, 34(12): 51-55(in Chinese) (李俊奎,王元珍.可重写循环滑动窗口:面向高效的在线数据流处理.  计算机科学, 2007, 34(12): 51-55)  WANG Shao-Peng, born in 1984, Ph.D. candidate.  His  research  interests  include data  stream,  event  stream  and  data mining.  WEN Ying-You, born in 1974, Ph.D., associate professor. His research  interests  include  the  next  generation  network,  and wireless sensor networks.  ZHAO Hong, born in 1954, Ph.D., professor, Ph.D. supervisor. His  research  interests  include  network  management,  and multimedia.  Meng  Ying-Hui,  born  in  1984,  Ph.D.,  lecturer.  His  research interests include wireless sensor network, sensor localization.   Background Disjoint query over data stream plays an important role in many  practical  applications,  such  as  finicial  analysis,  network monitoring, mobile services, and sensor network  management. The aim of Disjoint query is to find out all subsequences which are  similar  to  the  given  query  sequence and  not overlap with each other in the data stream, each of these subsequences is the 24  计  算  机  学  报  2016年 local best.   However,  few  of  the  current  relavant  works  focus  on  the Disjoint  query  based  on  sliding  window  over  data  stream. Although the methods based on existed studies can be taken to handle  this  problem, they  are  low efficiency,  because  the execution  process  over  each window  is  independent  to  each other,  and  does  not  have  the  characteristic  of  incremental computations.  In  this  paper,  we  addressed  Disjoint  query precise processing based on the sliding window without global warping  constraints  over  data  stream,  which  is  known  as DQ-SW  query. After  the  relationship between  query  results  of adjacent  two  windows  is  infered  by  analyzing  FSM  algorithm execution  processes  over  them, The DQPIC (DQ-SW  query processing  algorithm  with  incremental  calculation)  algorithm which is used to handle the DQ-SW query is proposed based on it, and  has  the  characreristic  of  incremental  calculations. The extensive  experiments  on  common  data  sets  SST  and maskedchirp  have  evaluated  the  proposed  algorithm  and verified  the  validity  of it.  Compared  with  the  current  other algorithms, it can not only guarantee the accuracy of the query results,  but  also  can  improve  the  time  efficiency  by  2.5~25 times at the cost of increment of space cost by 1.12~3.27 times. In  the  application  scenario  which  is  related  to the  Disjoint query based on the larger sliding window over data stream, the proposed algorithm has better performance. This  work  is  supported  by  the  National  Natural  Science Foundation  of  China(60903159,61173153,61402096,6150140 5) , the Special Fund from the Central Collegiate Basic Scienti fic  Research  Bursary(N110818001,N100218001,  N13050400 7,N120104001), the Science and Technology Plan of Shenyang (1091176-1-00), and the  National  High  Technology  Research and Development Program of China (2015AA01 6005). The  authors  of  this  paper  have  been  engaged  in  the researches of  the  data  processing,  event  processing  and  data mining over data stream. These studies are the key parts in all researches  related  to  programs  above  and  have  laid  the important theoretical basis and background knowledge, and the prototype  system  about  data  processing  and  event  processing over data stream has also been constructed.