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

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

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

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

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

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

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

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

数据流滑动窗口聚集查询降载策略研究*

滑动窗口聚集查询在数据流管理系统中应用广泛,数据流到达高峰期,必须考虑滑动窗口聚集查询中出现的降载问题。分析了子集模型的特点和已有降载策略的不足,给出了数据流滑动窗口聚集查询降载问题的约束条件,提出了能保证子集结果产生的基于丢弃窗口更新策略的降载算法。理论分析和实验结果表明,该算法对数据流滑动窗口聚集查询降载问题的处理具有较高的有效性和实用性。     

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

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

基于数据流的滑动窗口机制的研究

传统的关系数据库是在持久稳定的数据集合上进行数据查询，而数据流的长度是无界的，不可能将所有的数据存储下来，因此对数据流的查询处理大多采用了持续查询。对数据流进行持续查询时，往往感兴趣的不是所有的数据而是最近到达的部分数据，这样就引入滑动窗口模型。定义滑动窗口语义是数据流管理系统中一个非常基础性的工作，直接关系到数据流的存储和查询的执行效率。针对滑动窗口的模型和语义进行了研究。     

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

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

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

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

n-of-N 数据流模型上高效概率Skyline 计算

研究概率数据流上的q-skyline计算问题.与只支持滑动窗口数据流模型的已有方法相比,所提出的方法能够支持更为通用的n-of-N数据流模型.采用将q-skyline查询转换为区间树上刺入查询的方法支持n-of-N数据流模型.提出PnNM算法维护支持n-of-N数据流模型所需的相关数据结构,高效处理了不确定对象候选集合更新和区间更新等维护工作;提出PnNCont算法实现连续查询处理.理论分析和实验结果表明,算法能够有效地支持概率数据流n-of-N模型上的q-skyline查询处理.     

一种基于多时间粒度的数据流建模方法

在很多领域中，越来越多的数据以数据流的形式存在于各种应用当中，这些数据的特点是实时的、连续的、时变的、快速的。由于这些特点，在数据处理方法上引入了很多挑战性问题。本文重点从多时间粒度的角度研究了数据流建模问题，提出了多时间粒度的数据流滑窗建模方法，采用层次窗口模型对数据流进行描述，有效解决了Ad-Hoc查询
中的历史数据管理问题。     

带权值数据流滑动窗口随机抽样算法的改进

通过改进加权抽样算法,结合基本窗口技术,提出了两种面向带权值数据流上连续更新滑动窗口的随机抽样算法:WRSB算法和IWRSB算法。当新的数据元组到达时,根据数据元组的权值计算出该元组的键值,根据元组键值的大小决定其是否进入样本集以及样本集中被替换的数据元组,同时设置一个系统缓冲区来保存最近到达的键值较大的部分数据元组,作为过期数据元组的后备,使算法能够有效地处理过期数据元组问题。理论分析和实验结果表明,两种算法都能有效地处理带权值数据流上连续更新滑动窗口的随机抽样问题,相比较而言,IWRSB算法具有更好的性能。     

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

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

流和滑动窗口模型下的直径计算

直径作为图的一个重要属性,旨在提出一种在数据流环境下计算不同大小的滑动窗口直径的算法机制.基本思想是:在一维上采取较容易实现的精确算法,主要体现在只保存现在组成了直径和未来可能成为直径的元素;高维时通过投影到低维的方法计算出滑动窗口直径的近似值,并且可以通过投影的个数控制近似解的精度.最后通过对实验数据的分析和解释得到了若干有益的结论,为进一步的研究工作奠定了基础.