一种基于滑动窗口的数据流相似性查询算法

相似性查询是一种非常重要的数据挖掘应用。由于数据流具有无限、高速等特性,传统的查询算法不能直接应用于数据流。提出了一种基于小波滑动窗口的多数据流相似性查询算法。算法首先将滑动窗口划分成若干等宽基本窗口,然后对每个基本窗口内的数据进行小波分解与系数约简,从而形成小波摘要窗口。执行相似性查询时,直接基于小波摘要进行计算,而无需数据重构。由于利用了小波分解的线性处理优点,算法具有较低的时间复杂度。最后,基于实际数据对算法进行了实验,实验结果证明了算法的有效性。     

数据流查询处理中一种共享的分级窗口维护策略

由于数据流具有无界的特性,数据流系统中的查询多为带有窗口的查询,对带有窗口的查询,现有方法常由操作符直接维护窗口,但操作符的类型及排列方式可能会导致窗口难以维护,且冗余度较大.因此提出一种查询处理中的分级窗口维护策略,将窗口分为流窗口和操作符窗口,以流窗口为主并控制操作符窗口的维护,使查询中的窗口保持一致,解决了窗口维护问题,并且符合流查询语言的语义,各级窗口中的数据通过共享来解决内存消耗问题.     

数据流上多滑动窗口聚集查询的优化算法

在数据流的查询处理中,聚集查询是一种常用的查询类型.系统经常需要在同一个数据源上处理多个聚集查询,而单独地执行每个查询会导致严重的可扩展性问题和性能问题,因此实现相似查询之间的资源共享变得至关重要.针对多个具有不同时间窗口的聚集查询,本文提出了一种优化的窗口聚集算法OPWA(Optimized Paired Window Aggregation).先根据各时间窗口参数对聚集查询进行分组,使得相似查询可以同步调度;再采用paired技术对数据流进行分割.一方面减少了时间切片的数目,降低了空间的需求;另一方面同步地执行相似查询,减少了系统的计算开销.实验表明OPWA具有较好的性能.     

支持截止期敏感应用的数据流任务调度方法

当前,数据流上的实时处理系统大多关心平均元组延时最小化要求,而很少考虑每个元组的截止期要求.提出一种实时的自适应批任务调度策略--ATS(adaptive batch task scheduling),以支持时变突发的数据流上关键任务的严格截止期需求.ATS调度策略可以降低调度开销和过期处理开销,从而实现截止期错失率最小化和有效任务完成率最大化.提出了最优调度单位概念--批粒度,设计了闭环反馈控制机制,以在不可预测的数据流环境中自适应地动态选择最优批大小.理论分析和实验表明了ATS批调度策略的有效性和高效性.     

滑动窗口数据流上多极值查询资源共享策略研究

为了提高在同一数据流上同时计算多个连续极值查询(MAX或MIN)时的处理能力,对查询间资源共享技术进行了研究.提出了一种称为"关键点集"的裁剪策略,系统仅需保存少量数据即可满足所有查询的需要.发掘多个查询间的相似性和可共享的计算存储资源,提出了一个多极值查询处理算法MCEQP.采用链表结构实现的该算法,当一个新数据到达时最多需要O(M K)时间即可更新全部K个查询的结果,其中M为关键点集包含数据的个数.MCEQP采用触发器驱动的方式,只在某些特定时刻才需要计算因数据失效引起的查询结果变化,更新K个查询结果所需时间为O(K).理论分析和实验证明,对于滑动窗口数据流上的多个极值查询,MCEQP算法在降低存储开销和提高性能方面均优于现有的通用方法.     

一种数据流滑动窗口范围连接上基于局部特征的查询索引

在数据流上的连续查询操作中,连接操作是比较重要的一类操作.数据流上数据的变化总体上呈现一个连续性,并且在很多实际的情况下变化是逐渐发生的.数据流系统中的局部性可以表现为数据之间的局部性及连续查询之间的局部性.认为这些特性可以被用来提高数据流系统和应用当中的查询处理性能,尤其是研究相对较少的范围连接.提出的一种基于局部特征的数据流滑动窗口的范围连接索引,充分考虑了用户提交的查询所带有的局部性特征和数据流本身局部性特征,设计了LAQI结构来提高范围连接性能,然后在此基础上提出了LAAQI结构,并针对周期更新滑动窗口提出了范围连接的相应策略.实验证明,这些策略相对于传统范围的连接方法具有很好的性能.     

基于滑动窗口的数据流连续J-A查询的处理方法

数据流滑动窗口连接聚集连续查询(简记J-A查询)是经常使用的一类查询.这类查询的直观处理方法是创建查询操作树,以流水线的方式计算查询结果.这种方法需要在主存中保存滑动窗口连接的结果,查询处理的主存空间开销为O(α×β),其中(,(为参加连接两个滑动窗口的大小.在数据流的查询处理中,内存是最重要的计算资源.提出了两种滑动窗口J-A连续查询处理算法--IC算法和TC算法,使得查询处理的空间开销降为Ο(α+β).理论分析和实验结果表明,所提出的算法具有更高的效率.     

基于滑动窗口的数据流压缩技术及连续查询处理方法

基于滑动窗口的连续查询处理是数据流研究领域的一个热点问题．已有的研究工作均假设滑动窗口内的数据能够全部保存在主存中,若滑动窗口内的数据量超过了可用主存空间,已有的查询处理方法则无法正常工作．提出两种数据流上的滑动窗口压缩技术,有效地降低了滑动窗口的存储空间需求．同时,给出了基于压缩滑动窗口的连续查询处理算法,理论分析和实验结果表明,这些算法具有很好的性能,能够满足数据流连续查询处理的实时性要求．     

基于滑动窗口的数据流反向查询方法

提出了一种基于滑动窗口的数据流动态索引方法——DS-索引,采用滑动窗口保存数据流的最新数据,利用AVL树对数据流的变化区间进行索引,有效地解决了数据流的反向查询问题。     

数据流上加权共享滑动窗口的连接查询处理算法

在数据流应用中,系统经常需要处理大量的滑动窗口连续查询,采用共享滑动窗口技术可以有效节省存储空间,提高系统整体的查询处理能力。但是共享滑动窗口技术会增大单个查询的响应延迟,降低单个查询的服务质量。针对这个问题,论文提出了加权共享滑动窗口的概念,并提出了三种优化的连接执行算法,优先响应重要的滑动窗口查询,从而提高了系统整体的服务质量。理论分析和实验结果表明论文提出的方法是行之有效的。     

数据流上的复合滑动窗口聚集算法

基于滑动窗口的聚集查询是数据流研究领域的一个热点问题。在已有的研究工作中,聚集算法都是针对立即执行的连续查询提出的,这些算法均是当数据流新到一个元组立即计算一次聚集结果。而在实际应用中,连续查询有时采取的是周期执行方式。论文针对周期执行的连续查询提出了复合滑动窗口聚集算法,即数据流新到一个元组,将它插入到基本窗口中,当基本窗口被插满时计算一次聚集结果。给出了非增量式和增量式两种算法。理论分析和实验结果表明增量式算法具有较好的性能。     

可重写循环滑动窗口：面向高效的在线数据流处理

滑动窗口是在线数据流处理中的重要技术和基础设施。针对当前基于向量模型的滑动窗口存在滑动过程中需要移动过多数据，而导致效率不高的问题，本文提出一种可重写循环的滑动窗口技术。该技术在滑动过程中不移动数据，而是采用重写的方式来完成数据更新，并且它能够与当前滑动窗口无缝集成。理论分析和实验对比表明，该技术有显著的效率提升，能够高效地应用于实际的数据流处理。     

基于滑动窗口的在线数据流增量聚集查询

增量查询技术由于能有效处理大量、快速、源源不断到达的数据流，因此备受关注。滑动窗口是动态数据流环境下的一种典型的窗口类型。该文研究了基于滑动窗口的数据流聚集查询，提出了一种新的增量聚集查询算法，采用了多种增量计算方法和查询共享技术，实现了多窗口资源共享。实验验证了该方法的有效性。     

数据流滑动窗口连接的卸载策略研究

随着数据流应用系统的快速发展,数据流管理系统对数据库技术提出了巨大挑战.针对数据流上的滑动窗口连接操作,提出一些新的卸载技术,使得系统在过载的情况下卸载连接结果少的元组,从而最大化输出结果.双窗口模型和辅助窗口统计信息的建立保证了预估连接结果的可靠性,同时应用线段树使卸载的判断更加高效.当流速过快、系统处理能力无法与之同步时,通过前端卸载和后端卸载的配合使用达到理想的语义卸载,得到最大子集的连接结果.实验验证该卸载策略的性能好于现有其他方法.     

基于滑动窗口的数据流闭合频繁模式的挖掘

频繁闭合模式集惟一确定频繁模式完全集并且数量小得多,然而,如何挖掘滑动窗口中的频繁闭合模式集是一个很大的挑战.根据数据流的特点,提出了一种发现滑动窗口中频繁闭合模式的新方法DS_CFI. DS_CFI算法将滑动窗口分割为若干个基本窗口,以基本窗口为更新单位,利用已有的频繁闭合模式挖掘算法计算每个基本窗口的潜在频繁闭合项集,将它们及其子集存储到一种新的数据结构DSCFI_tree中,DSCFI_tree能够增量更新,利用DSCFI_tree可以快速地挖掘滑动窗口中的所有频繁闭合模式.最后,通过实验验证了这种方法的有效性.     

挖掘数据流滑动时间窗口内Top-K频繁模式

由于数据流滑动时间窗口中流数据包含模式的支持度是动态变化的,很难给出一个合适的支持度门限来挖掘数据流滑动时间窗口内的频繁模式.在研究数据流滑动时间窗口内流数据变化特点的基础上,论文提出了一种挖掘数据流滑动时间窗口内Top-k频繁模式的方法,该方法能够在保证模式挖掘误差基础上快速删除窗口内不频繁模式信息,保留重要的模式信息,并能按照支持度降序输出Top-k频繁模式.仿真实验结果表明,该算法具有较好的效率和正确性,并优于其它同类算法.