分段加权的概念漂移检测方法

针对现有漂移检测方法无法平衡检测延迟、误报与漏报以及时空效率等问题,提出一个新的阶段转换阈值参数,在概念漂移检测中引入包含“稳定阶段-警告阶段-漂移阶段”的分段加权机制,对实例分阶段地赋予权重,并将该机制应用在双层滑动窗口中;然后基于Hoeffding不等式提出一种分段加权的概念漂移检测方法(MSDDM)。在人工数据集上,相较于FHDDM、HDDM等漂移检测方法,MSDDM能够更快地检测出突变与渐变概念漂移,同时又能保持较低的误检率与漏检率;在真实数据集上,MSDDM相较于其他方法在大部分情况下都具有最高的分类准确率。实验结果表明,MSDDM能够以较高的漂移检测性能和较优的时空效率检测出数据流中的概念漂移。

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

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

多数据流上共享窗口连接查询的降载策略

数据流模型作为一种新型的模型 ,在许多应用中扮演着重要的角色 基于数据流模型的查询处理技术也得到了广泛的研究 为了提高查询系统的性能 ,现有的研究成果主要可以划分为两类 :调度优化和降低负载方法 调度优化方法通过改变元组执行次序来提高查询性能 降低负载方法在负载超出系统处理能力时 ,通过减少输入流量来提高吞吐率 然而 ,同时运用这两种方法来提高查询性能的研究工作还很少 结合共享滑动窗口查询操作的调度优化方法和降低负载方法 ,提出了两种在burst环境下提高查询吞吐率的策略 :均匀降载策略和小窗口准确降载策略

数据流滑动窗口上的一种多聚集查询共享策略

基于如何提高多个聚集查询的查询效率,提出了一种共享链树结构的多查询聚集计算共享策略.利用每个滑动窗口逻辑地将链树划分成若干子树,它们各自根节点中的聚集值恰好就是每个查询对应的结果值.数据流上多个查询可以在同一棵链树上并发执行,避免了每个查询的重复建树.同时,利用链树本身可降低无用的重复比较的性质,使得多个查询在同一棵链树上只需进行少量更新比较就可求得每个查询的新聚集值.实验证明,多个查询共用同一链树结构,可以最大程度地共享资源,减小内存使用量,因此大大提高了数据流上的查询处理效率,加大了数据流上的任务吞吐量,改善了系统性能.

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

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

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

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

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

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

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

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

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

针对当前关于数据流加权最大频繁项集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算法更有时间优势.

基于WCF-tree加权滑动窗口数据流元项集挖掘

数据流挖掘是当今数据挖掘领域内热点研究问题。通常频繁项集的数据量大,影响挖掘结果的理解与应用,提出一种基于WCF-tree加权滑动窗口数据流元项集挖掘算法(TWEM算法)。首先,考虑到数据在不同时间窗口内的重要性,允许用户定义窗口个数和各窗口权值;其次,利用WCF-tree挖掘闭项集;最后,结合各等价类内项集与相应元项集支持度不完全相同,保持一种可估算的关系的特性,挖掘元项集。实验结果表明,TWEM算法缩小了搜索空间,提高了程序的运行效率。

复合滑动窗口连接算法

滑动窗口是对数据流进行连续查询处理、得出近似查询结果的一种常用的数据采样技术 .连续查询处理的执行方式有 2类 :一类是立即执行方式 ;一类是周期执行方式 .在已有的研究工作中 ,基于滑动窗口的连接算法都是适用于立即执行的连续查询 .提出了适用于周期执行的连续查询的复合滑动窗口连接算法 ,即CSWSNLJ算法和CSWSNHJ算法 .

数据流滑动窗口连接查询降载策略研究

主要研究了在有限内存条件下数据流滑动窗口的近似连接查询,即数据流滑动窗口连接查询的降载问题。通过对连接属性域的划分,根据数据元组的连接属性值在属性域中的数据分布来决定每个数据元组进入参加连接运算的滑动窗口的概率,给出了一种面向数据流滑动窗口连接查询的语义降载策略。与已有的语义降载策略相比,文中给出的降载策略所需的数据统计信息较少,连接运算的结果数据元组便于进一步进行其它查询处理,并且对于各种倾斜(skew)参数的数据分布和不同程度的系统超载都有较好的适应性。理论分析和实验结果表明,该降载策略对数据流滑动窗口连接查询的降载处理具有较高的有效性和实用性。

一种基于滑动窗口模型的数据流加权频繁模式挖掘方法

相对于传统的频繁模式挖掘,加权频繁模式挖掘能发现更有价值的模式信息。针对数据流中的数据只能一次扫描,本文提出了一种基于滑动窗口模型的数据流加权频繁模式挖掘方法 WFP-SW(Sliding Window based Weighted Frequent Pattern minig),算法采用WE-tree(Weighted Enumeration Tree)存储模式和事务信息,利用虚权支持度维持模式的向下闭合特性,同时获取临界频繁模式。对临界频繁模式进一步计算其加权支持度获取加权频繁模式,使得计算更新模式更加便捷。实验结果显示算法具有较高的挖掘效率并且所需的内存更少。

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

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

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

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

对数据流频繁项集挖掘算法WSW-Imp的改进

近年来随着新的应用的出现,比如网络流量分析、在线事物分析和网络欺诈检测等,对数据流的挖掘成了一个越来越重要的课题。对于数据流频繁项集的挖掘,目前绝大部分的研究都集中在传统的窗口模式下进行,即时间衰退窗口模式、界标窗口模式和滑动窗口模式。Pauray S.M.Tsai于2009年提出了一种新的窗口模式:加权滑动窗口模式,并设计了两个基于此窗口模式的数据流频繁项集挖掘算法WSW和WSW-Imp,其中WSW-Imp是对WSW算法的改进。在研究了加权滑动窗口模式以及WSW-Imp算法的基础上,对WSW-Imp算法作了进一步的改进,设计了算法WSW-Imp2,并从理论上证明了WSW-Imp2算法比WSW-Imp算法更高效,实验结果也表明了这一点。

动态数据流分析的在线超限学习算法综述

动态数据流分析是一个具有广泛应用价值的研究课题,在线学习方法是其中的一种关键技术。在众多在线学习方法中,在线贯序超限学习机(Online Sequential Extreme Learning Machine,OSELM)是一种新颖且实用的在线学习算法,目前已在动态数据流分析中得到了成功应用。首先,介绍了OSELM的理论基础和算法执行过程;然后,以动态数据流分析为应用背景,对各种改进OSELM算法进行了分类综述,包括基于滑动窗口的OSELM、基于遗忘因子的OSELM、基于样本加权的OSELM以及其他方法,重点论述了各类算法的设计思路和实现策略,并对其优缺点进行了比较和分析;最后,探讨了值得进一步研究的问题。

数据流系统连接降载研究

连接运算在数据流系统中扮演了关键角色,其执行方式与传统DBMS的连接运算不同,流连接降载策略与传统的网络降载也不相同,已开发许多连接降载策略。论文在介绍流连接运算、数据流及数据流系统的模型后,对连接降载时的系统约束、输出质量目标进行了正式阐述。提出连接降载策略的分类方法,并着重分析了目前一些较为重要的连接降载策略,指出其特征和应用范围。最后总结了好的连接降载策略应具有的特点及未来研究的发展趋势。

基于滑动窗口模型的数据流加权频繁模式挖掘算法

加权频繁模式挖掘比传统的频繁模式挖掘更加的具有实际意义,针对数据流中的数据只能扫描有限次的性质,提出了基于滑动窗口模型的数据流加权频繁模式挖掘方法WFP-SW,该算法中数据存储采用的是矩阵数据结构,通过矩阵之间的相关操作来产生加权频繁模式。实验结果显示,该算法在产生加权频繁模式的时候不产生冗余模式,比传统的频繁模式挖掘算法有更好的效率。

基于加权滑动窗口的数据流频繁项集挖掘算法

已有的滑动窗口数据流模型没有考虑过时数据和事务数量对挖掘结果的影响.针对该问题.提出了一种新的动态权值滑动窗口的数据流模型,并将该模型应用于数据流频繁项集挖掘中,设计了动态权值滑动窗口的频繁项集挖掘算法FIMDWS和改进算法FIMDWSW-Imp.通过实验对算法做了分析和评价.