数据流处理中一种自适应的直方图维护算法

目前数据流的处理成为数据库领域新的研究方向．由于数据流中的数据量大、速度快，传统的查询处理在这种情况下不再适用．这种环境中的查询只能是一种近似查询．直方图通常被用于描述数据的分布．给出了一种新的直方图维护算法。它适用于有限的内存并能保证一定的误差要求实验证明了算法的实用性和有效性．     

面向数据流滑动窗口的自适应直方图发布算法

差分隐私技术作为一种有效的隐私保护机制,已被广泛应用在诸多领域。目前已有的静态数据集和动态数据集上的直方图发布方法在处理数据流滑动窗口模型时,往往只能够通过对数据直方图信息添加统一噪声的形式来实现数据保护,这导致了它们在实际应用中存在数据可用性低、时间复杂度高等问题。针对这些问题,文中通过将数据流近似计数技术综合到差分隐私保护算法中,进而提出了一种面向数据流滑动窗口模型的自适应直方图发布方法APS(Adaptive Histogram Publishing Method for Sliding Window)。APS算法首先利用数据流近似计数方法来预测下一时刻滑动窗口内数据的分布信息;然后通过比较估计值与真实值之间的差异来选取合适的发布值;最后对排序后的直方图区间进行聚类处理,并优化其桶内数据的误差。理论分析显示,APS算法能够在减少隐私预算的同时,有效地提高数据的可用性和缩短运行时间。在两种不同的真实数据集上的实验结果也验证了APS算法在数据可用性和运行时间上显著优于现有的基于分组的直方图发布算法。     

基于合并-分裂策略的近似等深直方图增量维护

直方图在数据库领域有着广泛的应用,是一种常用的概要数据结构生成方法.首先提出了一个基于数据流界标窗口模型的近似等深直方图构建维护算法框架,该算法框架通过桶的合并一分裂实现近似等深直方图的增量维护;然后对三种不同的桶合并一分裂策略进行了比较和讨论;最后对该算法框架和三种不同的桶合并一分裂策略进行了实验分析.     

数据流变化的检测

通过对数据流的两个相邻窗口的比较,检测出绝对变化较大的元素,以此来描述流数据的变化。把单个窗口中的数据流划分成若干层,在每层上对数据值域进行分段。然后在每层上定义若干分段集合,并对分段集合进行求和运算。通过对两个窗口的概要结构进行合并,采用二分法,利相集合的分解,可以求得变化较大的元素。理论和实验证明,本算法利用对数空间有效地解决了数据流中变化较大元素的检测问题。     

一种面向数据流模型的流计数算法

在研究数据流过程中,基于现有的概要数据结构Bloom Filter,给出改进的K Bloom Filter结构,从理论上对假阳性误判进行分析,得出两者具有相同的在误判率f0下表示集合规模的上限n0,因此,K Bloom Filter的误判率在可控范围内。提出基于K Bloom Filter的流计数算法,与基于Bloom Filter的流计数算法相比,在相同的空间复杂度O(m)和插入操作时间复杂度O(k)情况下,该算法降低了统计结果的误差。     

数据流上的分位数近似算法研究

数据流是一种新型数据模型,广泛应用于交通流量监控、通信管理、传感器网络、股票分析、Web点击流等众多领域.近年来越来越多的学者关注于数据流上的分位数计算研究.由于流数据的连续、无界、易失等特性,存储完整的流数据信息并得到精确的查询结果几乎是不可能的.在实施查询计算时追求内存用量与查询精度之间的最佳均衡.设计了规范数直方图的概要数据结构以存储流数据的摘要信息,并在此基础上提出了单遍扫描的、联机的分位数近似算法,其时间和空间复杂度均线性于概要结构中桶的个数,而与数据流的长度无关,因而具有很好的可规模性.该方法在均匀分布的数据上取得了优良性能.分析了算法精度与内存需求的关系.实验结果表明该算法具有较精确的查询结果,具备良好的实用性和有效性.     

一种面向周期性概念漂移的数据流分类算法

数据流挖掘已在许多领域得到应用,概念漂移检测是数据流挖掘研究中的一个重点.目前关于数据流中的概念检测的研究虽然取得了很多成果,却没有充分考虑到数据流概念"周期性"出现的特点.针对周期性概念漂移的特点,提出了当"历史概念"重现时,利用对应的模型来对数据流进行分类的方法,从而减小模型更新的代价,加快分类预测的速度.实验证明这种方法提高了运行效率.     

一种分布式数据流系统负载平衡算法

分布式数据流系统中,当输入数据流速发生较大波动时,会引起部分节点过载,从而影响整个系统的数据处理能力。针对这个问题,该文分析了分布式数据流系统的特点以及现有负载平衡算法的局限性,提出了一种利用多层重叠结构进行负载信息收集和负载分配的平衡算法。该算法利用虚拟树形结构进行负载信息的收集和负载分配,具有较好的扩展性能。以环形虚拟结构中保存的节点相对位置信息为依据进行负载移动,从而有效降低系统的响应时间。实验结果表明该算法具有良好的负载平衡能力和一定的应用价值。     

一种面向数据流处理的VLIW阵列处理机设计

针对高密度数据计算的要求,提出了一种VLIW处理器阵列多芯片互联的简单方法,通过独特的微码结构,建立具有可配置特征的高速数据通道的控制模型,适合构建高性能的媒体处理器阵列,模型能有效地改善系统扩展所需要的灵活性,实现高带宽的存储器接口和高性能的总线控制结构,提高了数据存取的连续性和灵活性,避免了运行过程中大量不必要的系统中断和功能切换开销,可显著提高数据处理带宽。     

一种高效的数据流挖掘增量模糊决策树分类算法

数据流具有数据持续到达、到达速度快、数据规模巨大等特点,这些都给数据流挖掘领域的研究工作带来了新挑战,而其中分类算法更是当前的研究热点.Domingos等在VFDT中利用Hoeffding不等式很好地解决了在数据流上进行单遍扫描获取高精度决策树的问题.Gama等对VFDT进行扩展并实现了VFDTc,使系统能够处理连续属性.Peng等在传统数据挖掘环境下提出了基于模糊理论的连续属性平滑离散化方法.基于前述工作,作者设计并实现了一种基于线索化排序二叉树的增量模糊决策树分类算法fVFDT,其主要贡献有如下4点:(1)第一次设计并实现了数据流上的基于线索化二叉排序树(TBST)的连续属性处理方法.相比VFDT,fVFDT的样本插入时间复杂度由O(n2)降低到O(nlogn).当新样本到达时,VFDTc需要更新O(logn)个属性节点,而fVFDT只需要更新相应的一个节点即可;(2)改进了VFDTc连续属性的最佳划分节点选取的计算方法,使其时间复杂度由O(nlogn)降低到O(n);(3)根据Fayyad等的研究成果,相比VFDTc,fVFDT只需从更少的备选划分节点中选取最佳节点,备选划分节点数由O(n)降低到O(logn);(4)改进了传统数据挖掘环境下的基于模糊理论的连续属性平滑离散化方法,有效地处理了噪声数据,很好地提高了分类精度.     

数据流频繁模式挖掘研究进展

现实世界和工程实践产生了大量的数据流,这种数据不同于传统的静态数据,对其进行有效处理和挖掘遇到了极大的挑战.如何使用有限存储空间进行快速和近似的频繁模式挖掘是数据流挖掘的基本问题,具有非常重要的研究价值和实践意义,已经引起了国内外研究者的广泛关注.本文深入分析数据流中的频繁模式挖掘,对其特点和算法进行较为全面的总结和分类论述,并讨论了存在的主要问题和未来的研究方向.     

数据流频繁模式挖掘算法设计

介绍了数据流频繁模式的概念和定义,提出了数据流频繁模式挖掘算法的通用数据流处理模型,详细总结了数据流频繁模式挖掘算法的三种分类方式:"窗口模型"、"结果集类型"和"结果集精确性".基于这些分类方法提出了数据流频繁模式挖掘算法的设计立方体,该立方体不仅涵盖了现有的数据流频繁模式挖掘算法,还对设计新的算法具有指导意义.基于设计立方体,分析了设计算法时应当采取的有效策略,旨在为设计新算法提供一个有力参考.最后讨论了数据流频繁模式挖掘的进一步研究工作.     

分布式数据流挖掘的研究进展

随着通信技术和硬件设备的不断发展,尤其是小型无线传感设备的广泛应用,数据采集和生成技术变得越来越便捷和趋于自动化,研究人员正面临着如何管理和分析大规模动态数据集的问题。能够产生数据流的领域应用已经非常普通,例如传感器网络、金融证券管理、网络监控、Web日志以及通信数据在线分析等新型应用。这些应用的特征是环境配备有多个分布式计算节点;这些节点往往临近于数据源;分析和监控这种环境下的数据,往往需要对挖掘任务、数据分布、数据流入速率和挖掘方法有一定的了解。综述了分布式数据流挖掘的当前进展概况,并展望了未来可能的、潜在的专题研究方向。     

快速挖掘数据流中离群点

离群点检测是数据挖掘领域的一个重要分支,当前数据流的离群点检测研究越来越受到关注.为了快速准确地检测出数据流中离群点,提出一种在线数据流离群点检测算法ODDS(outlier detection in online data stream s).它利用数据与频繁模式的相异程度来度量数据的离群程度,通过构建ODDS-Tree树,能动态地更新数据流中候选离群点的离群信息.实验结果验证了该算法与其他同类算法相比具有较高的效率与优良的可扩展性能.     

多数据流上的连续分布式Top-k监测

近年来,分布式系统中的数据流监测是一个十分活跃的领域。研究了如何实现通用并且高效的分布式top-k监测,即在分布的多数据流中根据用户给定的排序函数连续监测最大的k个值。在实际应用中,用户给定的排序函数可能是任意的排序函数,然而,目前的分布式top-k监测技术只支持加法作为排序函数。提出了一种通用的支持任意的连续的严格单调的聚集函数的分布式top-k监测算法GMR。GMR的通讯代价和k无关。通过真实世界数据和模拟数据验证了GMR的效率。实验表明,GMR的网络通讯量比同类方法低一个数量级以上。     

孤立点检测算法及其在数据流挖掘中的可用性

孤立点（也称为噪声、异常点等）是那些不符合数据一般模型的数据,它们与数据集的其他部分不同或不一致。检测孤立点的主要目的是为了从数据集中找出那些不正常的观察结果。随着现实世界和工程实践中不断产生大量的数据流,在数据流上有效检测孤立点越来越引起国内外研究者的广泛关注。在系统地分析了目前国内外孤立点检测相关文献的基础上,本文对孤立点检测算法进行了较为全面的阐述,并就这些算法是否可以用于数据流上孤立点检测进行了深入探讨和研究,同时指出了这些算法存在的主要问题以及未来的研究方向。     

数据流的预测与分类研究

数据流的预测和分类技术在网络入侵发现、系统性能分析等应用中具有重要的应用。作者对近年来有关数据流预测和分类的进展做了总结,并提出了一个数据流的预测和分类的通用模型,可用于系统性能的实时预测与异常检测。     

数据流的核心技术与应用发展研究综述

在数据流基本概念的基础上,综述了数据流领域中主要的流模型、构造概要数据结构的算法、连续查询处理和优化技术等热点问题,以及数据流的应用发展。     

Testing and Spot-Checking of Data Streams

Abstract. We consider the tasks of testing and spot-checking for data streams . These testers and spot-checkers are potentially useful in real-time or near real-time applications that process huge data sets. Crucial aspects of the computational model include the space complexity of the testers and spot-checkers (ideally much lower than the size of the input stream) and the number of passes that the tester or spot-checker must make over the input stream (ideally one, because the original stream may be too large to store for a second pass). A sampling-tester [GGR] for a property P samples some (but usually not all) of its input and, with high probability, outputs PASS if the input has property P and FAIL if the input is far {from} having P , for an appropriate sense of ``far.' A streaming-tester for a property P of one or more input streams takes as input one or more data streams and, with high probability, outputs PASS if the streams have property P and FAIL if the streams are far {from} having P . A sampling-tester can make its samples in any order; a streaming-tester sees the input from left to right. We consider the groupedness property (a natural relaxation of the sortedness property). We also revisit the sortedness property, first considered in [EKK+] in the context of sampling spot-checkers, and the property of detecting whether one stream is a permutation of another (either directly or via the SORTED-SUPERSET property, a technical property that is equivalent to PERMUTATION under some conditions). We show that there are properties efficiently testable by a streaming-tester but not by a sampling-tester and other (promise) problems for which the reverse is true.     

数据流分类挖掘中的概念变化研究

数据流分类挖掘首先要面对概念变化问题。介绍了数据流分类中的概念变化的定义与类型,研究了概念变化的意义及应用,对目前数据流中处理概念变化的方法进行了综述。真实数据流常常含有大量的噪声,因此需要理解噪声与概念变化的区别。针对周期性数据流中概念重现现象,当"历史概念"重现时,利用特定的模型对数据流进行概念预测,可以减少模型更新的代价。