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

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

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

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

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

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

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

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

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

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

挖掘滑动窗口中的数据流频繁项算法

滑动窗口是一种对最近一段时间内的数据进行挖掘的有效的技术,本文提出一种基于滑动窗口的流数据频繁项挖掘算法.算法采用了链表队列策略大大简化了算法,提高了挖掘的效率.对于给定的阈值S、误差ε和窗口长度n,算法可以检测在窗口内频度超过Sn的数据流频繁项,且使误差在εn以内.算法的空间复杂度为O(ε-1),对每个数据项的处理和查询时间均为O(1).在此基础上,我们还将该算法进行了扩展,可以通过参数的变化得到不同的流数据频繁项挖掘算法,使得算法的时间和空间复杂度之间得到调节.通过大量的实验证明,本文算法比其它类似算法具有更好的精度以及时间和空间效率.     

基于衰减滑动窗口数据流聚类算法研究

数据流具有数据流量大、流量连续且快速、难以存储和恢复等特性,其挖掘质量和效率是检验挖掘算法的重要标准.传统的数据流聚类挖掘算法是基于界标窗口、滑动窗口和衰减窗口模型,其算法的聚类质量较差,时间复杂度高等不足,就此类问题,研究一种滑动衰减窗口的数据流聚类算法,并对算法进行了设计与实现,有效的改善传统数据流算法聚类质量和时间效率的问题.仿真实验结果表明了该算法的有效性,达到了较满意的效果.     

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

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

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

针对数据流的特点,根据Moment算法提出一种基于频繁闭项集挖掘的增量式维护算法。该算法通过滑动窗口增量更新数据流中的事务,采取一种高效的项的位序列表示方法降低窗口滑动的时问和空间复杂度,应用压缩的模式树进行频繁闭项集检查,以确保挖掘结果的准确性。实验证明了该方法的有效性。     

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

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

数据流上的预测聚集查询处理算法

实时数据流未来趋势的预测具有重要的实际应用意义.例如,在环境监测传感器网络中,通过对感知数据流进行预测聚集查询,观察者可以预测网络覆盖的区域在未来一段时间内的平均温度和湿度,以确定是否会发生异常事件.目前的研究工作多数集中在数据流上当前数据的查询,数据流上预测查询的研究工作还很少.采用多元线性回归方法,给出了数据流上的聚集值预测模型,提出了一种数据流预测聚集查询处理方法.当预测失败的次数大于预先给定的阈值时,给出了一种预测模型自动调整策略,以降低预测误差.还提出了滑动窗口的更新周期、数据流的流速对预测精度影响的数学模型.理论分析与实验结果表明,提出的预测聚集查询处理算法具有较高的性能,并且能够返回满足用户精度要求的预测查询结果.在实验中,采用TPC-H国际标准测试数据和TAO(tropical atmosphere ocean)测量的海洋表面空气温度数据来构造数据流.     

基于滑动窗口的进化数据流聚类

提出了纳伪(false positive)和拒真(false negative)两种聚类特征指数直方图分别来支持纳伪误差和拒真误差窗口的聚类分析;然后,提出一种基于滑动窗口的数据流聚类方法.该方法在占用窗口大小的次线性内存空间前提下,及时保存最近数据记录的分布状况,从而实现对滑动窗口内的数据进行聚类.此外,它还可被扩展用于N-n窗口(滑动窗口的扩展模型)的数据聚类.实验采用KDD-CUP'99和KDD-CUP'98真实数据集以及变换高斯分布的人工数据集构造进化数据流.理论分析和     

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

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

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

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

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

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

挖掘数据流任意滑动时间窗口内频繁模式

由于数据流的流动性与连续性,数据流所蕴含的知识会随着时间的推移而发生变化.因此,在绝大多数数据流的应用中,用户往往对新产生的流数据所包含的知识要比对历史流数据所包含的知识感兴趣得多.提出了一种挖掘数据流任意大小滑动时间窗口内频繁模式的方法MSW(mining sliding window).当数据流流过时,该方法使用滑动窗口树SW-tree在单遍扫描流数据的条件下及时捕获数据流上最新的模式信息.同时,该方法还周期性地删除滑动窗口树上过期的及不频繁的模式分支,从而降低滑动窗口树的空间复杂度与维护代价.此外,该方法还应用时间衰减模型逐步降低历史事务模式支持数的权重,并由此来区分最近产生事务与历史事务的模式.大量仿真实验的结果表明,算法MSS具有较高的效率与优良的可扩展性,同时也优于其他同类算法.     

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

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

Outlier Detection over Sliding Windows for Probabilistic Data Streams

Outlier detection is a very useful technique in many applications, where data is generally uncertain and could be described using probability. While having been studied intensively in the field of deterministic data, outlier detection is still novel in the emerging uncertain data field. In this paper, we study the semantic of outlier detection on probabilistic data stream and present a new definition of distance-based outlier over sliding window. We then show the problem of detecting an outlier over a set o...     

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

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