一种基于变窗口的数据流连续查询方法

目前对数据流连续查询的研究工作大部分基于滑动窗口,窗口大小固定不变.本文从内存资源有限性与查询结果精确性角度出发,采用可变窗口技术,在缓存中加入窗口控制器,当数据到达缓存时,根据用户提出查询具体问题和数据流速情况,窗口分配算子对其进行窗口大小的划分.使得在内存资源有限的情况下,通过动态改变滑动窗口大小,充分利用系统资源,降低内存使用率的同时,使连续查询的查询结果都在允许的误差范围内,此方法经过验证是可行的.     

一种基于可变滑动窗口的数据流分段聚类算法

数据流的应用越来越广泛,数据流挖掘成为数据挖掘的重点研究方向之一。在分析各种数据流聚类算法的基础上,提出了一种基于可变滑动窗口的数据流分段聚类算法。算法以时间序列数据流模式表示技术为参考,以去除噪音和压缩数据为目的,实现了数据流的特征提取和概要存储。实验表明,算法具有低时空复杂度、自适应等特点。     

支持复杂语义的数据流滑动窗口连接建模和查询优化

数据流连接操作的执行方式直接影响到查询执行的效率和结果的正确性.在STREAM项目流化方法的基础上,对复杂应用下的数据流滑动窗口连接的准确语义进行了分析和建模,以时间窗口连接的增量维护为例提出了两种改进的基本维护策略,给出了针对元组窗和分组窗的维护方法,讨论了根据参数和环境的不同进行适应性的维护.实验证明了在不同的窗口、流速和选择度下,适应性地选择不同的优化算法会达到最优的处理性能.     

时间滑动窗口上数据流极值聚集的空间优化

传统的数据流极值聚集方法在极端情形下为获得连续的精确解,会因维护大量候选项而导致巨大的内存开销,为此文中提出了一种时间滑动窗口上内存有界的极值聚集方法.在候选项数量达到指定阈值时,该方法随机抽样新到达窗口的数据,使得内存维护有限数量的候选项,连续返回极值近似解.设计了一种空间有界的摘要数据结构REx-link,可以在有界的内存中基于随机抽样进行维护,实现时间滑动窗口上的数据流极值聚集.从理论上证明了随机算法的出错概率存在上界,并通过仿真实验分析了算法的返回结果与精确解的近似程度.分析表明,计算精度和空间开销的折中是实际应用可接受的.     

数据流滑动窗口连接的自适应降载策略

连接操作是一种应用广泛的查询类型,在对DSMS进行降载时,必须考虑连接查询的降载问题.针对滑动窗口连接查询,构建一种基于不同等级基本窗口的滑动窗口内部结构.采用部分连接的方式实现CPU过载情况下的降载,采用基于基本窗口重要性的语义丢弃方式实现内存不足情况下的降载.实验结果表明所采用的算法有效.     

一种基于滑动窗口的一趟数据流聚类算法

在海量的动态数据流中发现有价值的知识,是数据挖掘技术研究的重要问题.研究数据流聚类,根据数据流的特点,提出了一种基于滑动窗口的一趟数据流挖掘的算法,对原有的一趟数据流聚类算法进行了改进,增强了一趟数据流聚类算法的扩展性,改进了数据流聚类的质量.     

数据流窗口查询语义的局限性及改进方法

在数据流处理系统普遍使用滑动窗口查询模型来解决数据流的持续查询问题.对一些特殊的查询类型,在使用滑动窗口查询时无法完全达到查询要求,通过引入条件窗口对滑动窗口模型进行更一般化的扩展和改进,可以解决滑动窗口语义在处理这一类型查询中的局限性.     

数据流上的轮廓查询算法

采用滑动窗口技术对数据流进行近似,提出了两种数据流上的轮廓查询方法:CCS算法和PCS算法.CCS算法能够实时反映数据的变化,内存空间的利用率也较高.PCS算法则适合周期性更新的应用环境,有利于节约CPU资源.实验结果证明所采用的算法是有效的.     

一种基于混沌理论的数据流连续聚集查询预测算法

为了有效地预测聚集查询的未来聚集值,提出了一种基于混沌理论的数据流连续聚集查询预测未来聚集值算法——CSPA算法.数据流看作是以数据到达时间为序的一个时间序列,借鉴传统时间序列分析技术探讨了连续聚集查询的未来聚集值预测问题,但由于数据流序列与传统时间序列在时间间隔和数据集的处理上存在很大差别,于是采用流滑动窗口技术加以处理.其次,针对目前数据流聚集查询预测领域已有的一些研究结果都未考虑流数据内在的复杂非线性动力学特征对预测的影响问题,该算法又利用了混沌理论中的局域预测思想解决了这一不足.实验结果表明,利用该算法进行预测具有很好的准确性.     

滑动窗口内动态数据流聚类算法研究

滑动窗口是数据流中一种关注近期数据的近似方法,提出一种采用滑动窗口处理数据的优化算法SWStream。在线阶段利用滑动窗口树存储概要结构,动态调整窗口大小。优化后的算法能及时淘汰过期元组,同时对新到达的元组不断进行实时处理,可以获得更准确的分析结果。而在离线阶段对上一阶段的结果进行宏聚类,得到最后的结果。与聚类算法CluStream相比,此算法处理数据的效率更高,也相对节约内存。     

Linked-Tree： An Aggregate Query Algorithm Based on Sliding Window over Data Stream

How to process aggregate queries over data streams efficiently and effectively have been becoming hot re search topics in both academic community and industrial community. Aiming at the issues, a novel Linked-tree algorithm based on sliding window is proposed in this paper. Due to the proposal of concept area, the Linked-tree algorithm reuses many primary results in last window and then avoids lots of unnecessary repeated comparison operations between two successive windows. As a result, execution efficiency of MAX query is improved dramatically. In addition, since the size of memory is relevant to the number of areas but irrelevant to the size of sliding window, memory is economized greatly. The extensive experimental results show that the performance of Linked-tree algorithm has significant improvement gains over the traditional SC （Simple Compared） algorithm and Ranked-tree algorithm.     

自适应窗口滑动的物联网数据流典型相关分析

针对传统的数据流典型相关分析算法没有考虑数据流速率的动态变化特性,不适用于物联网实际情况的问题,提出一种基于自适应窗口滑动的数据流典型相关分析算法,依据数据流速率变化,设计自适应的窗口滑动策略,并动态调整滑动窗口。实验结果表明,可以保证物联网数据流典型相关分析的实时性、准确性和高效性。     

滑动窗口下数据流完全加权最大频繁项集挖掘

针对当前关于数据流加权最大频繁项集WMFI(weighted maximal frequent itemsets)的研究无法有效地处理频繁阈值和加权频繁阈值不一致情况下WMFI的挖掘问题,提出了完全加权最大频繁项集FWM FI(full w eighted maximal frequent itemsets)的概念.为了减少naive算法在处理滑动窗口下完全加权最大频繁项集挖掘时存在的冗余运算,提出了FWMFI-SW(FWMFI mining based on sliding window over data stream)算法.所提出的算法通过基于频繁约束条件的优化策略减少了naive算法中M ax W优化策略的无效调用次数;采用编辑距离比率作为WMFP-SW-tree的重构判别函数,可以有效减少该树的重构次数.实验结果表明FWMFI-SW算法是有效的,且比naive算法更有时间优势.     

A graph based sliding window multi join over data stream

Join operation is a critical problem when dealing with sliding window over data streams. There have been many optimization strategies for sliding window join in the literature, but a simple heuristic is always used for selecting the join sequence of many sliding windows, which is ineffectively. The graphbased approach is proposed to process the problem. The sliding window join model is introduced primarily. In this model vertex represent join operator and edge indicated the join relationship among sliding windows. Vertex weight and edge weight represent the cost of join and the reciprocity of join operators respectively. Then good query plan with minimal cost can be found in the model. Thus a complete join algorithm combining setting up model, finding optimal query plan and executing query plan is shown. Experiments show that the graphbased approach is feasible and can work better in above environment     

A graph-based sliding window multi-join over data stream

Join operation is a critical problem when dealing with sliding window over data streams. There have been many optimization strategies for sliding window join in the literature, but a simple heuristic is always used for selecting the join sequence of many sliding windows, which is ineffectively. The graph-based approach is proposed to process the problem. The sliding window join model is introduced primarily. In this model vertex represent join operator and edge indicated the join relationship among sliding windows. Vertex weight and edge weight represent the cost of join and the reciprocity of join operators respectively. Then good query plan with minimal cost can be found in the model. Thus a complete join algorithm combining setting up model, finding optimal query plan and executing query plan is shown. Experiments show that the graph-based approach is feasible and can work better in above environment.     

一种基于预裁剪的不确定数据流频繁项集挖掘算法

随着交通、网络流量监控等应用的涌现,不确定数据流频繁项集挖掘成为近年来的研究热点。通常在不确定数据流中,频繁项集所占的比例较小,导致挖掘中无效操作较多。基于这种情况,提出了一种基于预裁剪的不确定数据流频繁项集挖掘算法Prep-UF-Streaming;该算法,不仅能裁剪掉大部分非频繁项集,提高了算法的平均运行时间;而且能够检测到非频繁项集成为频繁项集的可能性,尽量不丢失频繁项集,从而尽可能地提高算法的性能。     

一种面向空间数据的聚集查询处理方法

提出一种新的面向空间数据的聚集查询处理方法。该方法扩展了AMH和AMH*方法,首先将整个空间栅格化,再将若干频数接近的邻居栅格组合成遵循一定约束条件的桶。随着数据分布变化,各桶不断重组或者拆分,具有空间复杂度低、查询精度高等特点。理论分析与实验结果均表明新方法优于现有方法。