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

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

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

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

基于滑动窗口的数据流连接聚集查询降载策略

基于单个数据流的滑动窗口聚集查询降载技术和数据流连接技术,提出滑动窗口模型下的数据流连接聚集查询降载策略,给出判断系统是否过载的负载方程和使过载系统恢复到轻载状态的降载算法,使降载后的查询结果同时拥有较小的相对误差和最大的元组输出率。实验结果表明,该降载策略具有较好的可行性和适应性。     

一种数据流上基于滑动窗口的点连接查询处理算法

连接是数据库研究中至关重要的一环,在没有边界、连续的数据流模型中,由于存储有限和实时性需求,连接算法主要基于滑动窗口作近似处理.主要研究数据流上一种特殊的连接,命名为点连接.点连接是指对于任意r∈R(称为主流),有唯一的s∈S(称为副流)与之对应,其中s.a=r.a且s.time最接近r.time(time称为时间特征).因此,流R与流S上的数据属于n∶1的关系.而在真实的分布式环境下,因为网络等原因,流数据到达的时间和顺序往往不一致,导致连接成功率下降.提出一种新的连接查询处理算法,能够在复杂的网络环境下获取更多的连接输出.实验模拟了2种网络环境,分别在数据有序到达和数据乱序到达2种情况下对算法验证,证明此算法比已有算法更优.     

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

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

一种数据流上截止期敏感的滑动窗口处理策略

在数据流上定义了截止期作为连续查询的实时约束,并建立了基于截止期的滑动窗口处理模型;提出了一种基于预测的截止期敏感的滑动窗口处理策略;在多滑动窗口查询处理环境中,提出了一种（k,m ）截止期约束机制,在提高查询实时性的前提下,尽可能的满足不同查询对结果丢失率的不同约束。实验结果表明该处理策略能够有效提高数据流上滑动窗口查询的截止期满足率。     

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

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

分布式数据流连接查询算法

分布式处理是数据流管理系统发展的必然趋势。文章研究了分布式数据流的连接查询，提出DM3Join算法，它由2部分组成：一是通过分解并发的连接请求，合并相同的连接谓词，形成分布式查询操作算子；二是数据流在各分布式代理(Agent)中流转实现部分连接，并在查询引擎处组合成最终结果。DM3Join算法采用了一种类似路由表的结构执行窗口连接，由于可以共享中间结果，算法只需扫描数据1遍。分析和实验证明，该连接算法是高效的。     

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

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

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

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

多数据流滑动窗口并发连接方法

提出一种多数据流滑动窗口连接方法M3Join及其实现架构Roujoin. Roujoin由一个连接路由表和多个连接区组成,其内容根据并发连接请求设置,先将新元组插入缓冲区,然后根据其路由标记查找连接路由表进入合适的连接区执行连接或输出给用户.如果产生连接元组,则更改其路由标记后送回连接路由表,并反复迭代直到没有连接元组.由于共享中间结果,在处理多个并发查询时只需扫描流元组一遍.实验结果表明M3Join具有良好的性能,能够满足并发连接查询处理的需求.     

基于概率模型的数据流预测查询算法

挖掘在线数据流的变化趋势并预测未来时间窗口上的可能值,可以为许多时间敏感的应用提供重要决策支持.通过将数量可能无限的流数据元素映射到离散的且数量有限的流数据状态空间,不断变化的流数据变化趋势可以模拟成连续的流数据状态变化的过程,进而在很小的时间与空间代价下,数据流状态变迁的趋势动态存储在状态变迁图中.通过分析状态变迁图中的流数据变迁的统计规律,数据流上未来时刻的可能值可以应用马尔可夫模型在线连续预测.     

基于概率衰减窗口模型的不确定数据流频繁模式挖掘

考虑到不确定数据流的不确定性,设计了一种新的概率频繁模式树PFP-tree和基于该树的概率频繁模式挖掘方法PFP-growth.PFP-growth使用事务性不确定数据流及概率衰减窗口模型,通过计算各概率数据项的期望支持度以发现概率频繁模式,其主要特点有：考虑到窗口内不同时间到达数据项的贡献度不同,采用概率衰减窗口模型计算期望支持度,以提高模式挖掘准确度;设置数据项索引表和事务索引表,以加快频繁模式树检索速度;通过剪枝删除不可能成为频繁模式的结点,以降低模式树的存储及检索开销;对每个结点都设立一个事务概率信息链表,以支持数据项在不同事务中具有不同概率的情形.实验结果表明,PFP-growth在保证挖掘模式准确度的前提下,在处理时间和内存空间等方面都具有较好的性能.     

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

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

基于最小生成树的数据流窗口连接优化算法

与传统关系数据库不同,数据流管理系统主要处理并发的连续查询.由于查询可能随时增删,所以其主要关注适合查询增删的并发连续查询优化,而不是单条查询优化.提出适合频繁增删查询环境下的数据流窗口连接优化算法.对于新注册的查询以类似最小生成树算法写出数据流的探测序列,然后在不更改其他查询探测序列顺序的情况下尽量合并,减少重复计算.注册或删除查询并不影响其他的查询计划,不需要执行繁琐的查询计划迁移.理论分析和实验证明,该算法简单,优化性能在可接受的范围内,尤其适合查询更新频率较高的系统.     

一种基于滑动窗口的数据流频繁闭项集挖掘算法

频繁项集挖掘是数据流挖掘中的一个热点问题.提出了一种新的数据流频繁闭项集挖掘算法MFCI-SW.首先设计了两个新的数据结构:频繁闭项集表FCIL和频繁闭合模式树MFCI-SW-Tree,在此基础上以滑动窗口中的基本窗口为更新单位,在每个基本窗口中提取出频繁闭项集的数据项,将其支持度F和窗口序列号K存到FCIL中;然后随着新基本窗口的到来,通过删除频繁闭项集表中K值最小的数据项和插入新数据项完成对FCIL的更新和MFCI-SW-Tree树的裁剪;最后在MFCI-SW-Tree中可以迅速挖掘出满足用户需要的频繁闭项集.实验结果证明了该算法在执行效率上明显优于DS-CFI算法.     

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

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