基于前缀树的数据流容错概要结构构造

应用于数据流环境的数据挖掘算法应首要考虑算法的时空复杂性,而要实现消耗巨大计算资源的容错模式挖掘则更要专注于算法的效率.容错模式挖掘是为了从被噪声干扰的真实世界数据中获取允许一定程度错配的、更加泛化的有用知识.提出一种新的单遍历、高压缩的容错前缀树形概要结构DSFT-tree(Data Stream Fault-Tolerant Frequent PatternTree),用来捕捉最近到达的数据流中的数据元素,并且能够高效移除过期数据,实现最大限度地降低计算资源消耗.利用滑动窗指针和位向量表达法实现容错树形概要结构的高效重构,并进一步基于滑动窗口技术实现了数据流环境下的容错频繁项挖掘.实验采用IBM数据发生器产生事务数据,在合理时间内最终挖掘频繁项的数量为FP-stream算法的1.5倍.

基于多层概要结构的数据流的频繁项集发现算法

利用一类基于异或运算的两两相互独立的哈希函数族,实现了对多层结构流数据进行“概括”的概要数据结构.应用该多层概要数据结构,实现了面向数据流的多层频繁项集的动态近似查找算法.实验结果表明,该算法以亚线性的时间和空间消耗,在统计意义上达到了几乎100%的查找和估计精确度.

基于概要数据结构可溯源的异常检测方法

提出一种基于sketch概要数据结构的异常检测方法.该方法实时记录网络数据流信息到sketch数据结构,然后每隔一定周期进行异常检测.采用EWMA(exponentially weighted moving average)预测模型预测每一周期的预测值,计算观测值与预测值之间的差异sketch,然后基于差异sketch采用均值均方差模型建立网络流量变化参考.该方法能够检测DDoS、扫描等攻击行为,并能追溯异常的IP地址.通过模拟实验验证,该方法占用很少的计算和存储资源,能够检测骨干网络流量中的异常IP地址.

一种基于自适应结构概要的有向标签图子图匹配查询算法

有向标签图作为重要的数据表示模型,广泛应用于社交网络、语义网分析等信息技术相关的研究领域,子图匹配查询是图数据管理的重要研究问题,引起了研究者的广泛关注.有向标签图的子图同构和子图模拟匹配查询由于代价极高,不适用于大规模图数据的查询处理.本文针对有向标签图,研究基于自适应结构概要的子图匹配查询算法.首先基于图压缩的思想,提出一种满足顶点"局部双拟"关系且具有自适应更新特性的有向标签图结构概要模型,在缩小数据图规模的基础上,适应查询图的结构;然后采用图模拟方式,提出基于自适应结构概要模型的子图匹配查询算法,根据查询图顶点的标签,对与其匹配的结构概要顶点按照其中包含数据图顶点的数量由小到大排序,根据查询图顶点之间的rank差值在结构概要模型中实现顶点匹配;最后在真实数据集和模拟数据集上进行实验,结果表明:(1)自适应结构概要模型可根据查询图结构,实现对数据图的最大压缩;(2)可在O(|E|log|V|)的总体时间复杂度内实现结构概要的自适应更新以及基于图模拟方式的子图匹配查询.

面向数据流的多层Count-Min概要数据结构

构造了多层Count-Min概要数据结构来概括流数据中的层次结构。通过定义多层数据域U*上两两相互独立的异或哈希函数族,将数据流元组映射到L×D×W的三维计数数组,L是层次个数,D是从哈希函数族中均匀随机选取的哈希函数个数,W是哈希函数的值域。基于该结构,利用广度优先查询策略,查找多层频繁项集和估计多层频繁项值。实验表明,该结构在更新时间、存储空间和估计精度方面比直接堆叠多个Count-Min结构有较大的提高。

基于概要数据结构的网络异常检测方法

提出一种基于概要数据结构(sketch)的网络异常检测方法。采用金字塔时间模型对高速网络数据流进行分析,并基于奇异熵提取sketch。统计一定周期内该数据结构的特征值变化趋势,计算出均值和梯度值,以及相应的报警区间。当告警出现时,该方法能分析出现异常的IP地址。实验证明,该方法能有效地对网络进行异常检测。

数据流概要数据结构在大型零售商业管理信息系统中的应用

本文首先介绍了数据流概要数据结构构建技术及其发展现状,说明了数据流概要构建技术应用于大型零售商业管理信息系统中的必要性,分析了如何将数据流概要构建技术应用于大型零售商业管理信息系统中。

基于概要数据结构的高维数据流聚类算法

为了在高维数据流中有效地形成聚类,针对经典算法CELL-Tree存在的问题,提出一种新的概要数据结构PL-Tree以及基于此数据结构的算法PLStream,并采取衰减窗口模式来适应数据流的变化,采用剪枝策略控制内存中聚类模型的规模.实验表明,PLStream算法能较好地适应高维数据流,比CELL-Tree算法具有更好的时间和空间效率.

基于概要数据结构的全网络持续流检测方法

持续流是隐蔽的网络攻击过程中显现的一种重要特征,它不产生大量流量且在较长周期内有规律地发生,给传统的检测方法带来极大挑战。针对网络攻击的隐蔽性、单监测点的重负荷和信息有限的问题,提出全网络持续流检测方法。首先,设计一种概要数据结构,并将其部署在每个监测点;其次,当网络流到达监测点时,提取流的概要信息并更新概要数据结构的一位;然后,在测量周期结束时,主监测点将来自其他监测点的概要信息进行综合;最后,提出流持续性的近似估计,通过一些简单计算为每个流构建一个位向量,利用概率统计方法估计流持续性,使用修正后的持续性估计检测持续流。通过真实的网络流量进行实验,结果表明,与长持续时间流检测算法(TLF)相比,所提方法的准确性提高了50%,误报率和漏报率分别降低了22%和20%,说明全网络持续流检测方法能够有效监测高速网络流量。

数据流上具有数据遗忘特性的小波概要

动态地维护数据流的概要结构是数据流查询和挖掘等处理工作的基础.在许多数据流应用场合,数据的影响随时间衰减,流中数据被逐步遗忘,称为数据流的遗忘特性.在数据流概要的构造中,应体现这种特性.离散小波变换是一种应用得较多的数据流概要构造方法.将数据流的遗忘特性引入小波概要的构造中,提出了一种能反映数据流遗忘特性的小波概要结构:基于小波的分层遗忘概要,分别讨论了误差平方和及最大绝对误差两种误差度量标准下这种概要的构造方法.所进行的实验验证了该概要的有效性.

基于Filter-ary-Sketch数据结构的骨干网异常检测研究

针对骨干网上异常检测的特殊要求,提出了一种基于Filter-ary-Sketch数据结构的异常检测方法。该方法通过Filter-ary-Sketch实时记录网络流量信息,然后每隔一定周期进行基于多维熵值的异常检测。如果出现异常则根据Filter-ary-Sketch记录的流量信息进行异常点定位,最后利用Bloom Filter中记录的源IP信息进行恶意流量阻断。该方法能够检测多种类型的网络攻击,且能有效地进行恶意流量阻断。利用实际骨干网流量数据,分别从效率和精度2个方法进行对比实验,取得了较好的效果。

基于Sketch数据结构的海量网络流量实时排名系统

海量互联网流量数据服从幂律分布,因此对流量中排名前k个的服务提供商(SP)进行实时监控和了解,有助于运营商实时了解网络状态,便于网络管理。针对这个事实,提出一种采用概要(Sketch)数据结构的互联网流量实时排名系统。该系统实时记录网络数据流信息到Sketch数据结构,用Sketch图来保留整个数据流所有元素的概要信息。与数据流所有元素信息相比,Sketch图占用更少的计算和存储资源,因此可以实现实时流量统计。此外,为适应大规模流式数据的需求,系统算法进行并行化,并部署在并行流式工作框架SparkStreaming之上,从而实现对海量网络流量的实时排名。该系统应用于运营商真实网络环境下,对真实网络环境下流量进行了实时跟踪和分析。通过大量实验首次给出了某省网络运营商真实流量的实时排名变化情况,发现在一天内流量排名虽然有小幅的变化,但整体排名顺序基本保持不变,腾讯公司是流量最大的服务提供商;同时还发现为了分流网络流量,减小网络流量压力,服务提供商将网页内嵌的图片、视频等对象转移到其他域名下。通过实际应用和测试验证了该实时排名系统的有效性。

一种基于高斯混合模型的不确定数据流聚类方法

传感器的广泛应用产生了大量的不确定数据流,在聚类应用中,当输入数据为连续型随机变量时,现有基于离散型随机变量的聚类方法无法满足数据流应用在效率和精度上的要求.使用高斯混合模型作为不确定数据的基本表示形式,仅需要保存不同组件的描述信息即可,可以更好地利用存储空间,完成对真实情况的逼近,在此基础上提出了一种可以发现时间维度上的不确定数据流聚类方法cumicro,该算法将时间直接作为数据属性,可直接查询某个时间维度的聚簇,避免了传统基于划分的聚类中较难发现非球状聚簇的问题.通过实验与经典算法umicro进行比较,证明了本文算法的有效性,并分析了不同K值、τ值下的聚类结果.最后得出结论,原始数据较密集时,相较原有基于离散模型的聚类,该算法具有准确度上的优势.

一种基于线性时间概率计数算法的数据聚集技术

无线传感器网络中,通过数据聚集操作在中间节点预先对数据进行处理,可去除大量冗余,减少数据传输,实现节能。针对多路径路由下数据聚集操作的重复计数问题,研究对副本不敏感的概要结构并优化某些特性,在线性时间概率计数算法的数学模型基础上提出一种新的数据聚集技术FA(Fan Aggregation)技术,实现高能效的数据聚集。理论分析和仿真实验均表明,FA技术相较于FM(Flajolet Martin)技术和LC(Linear Counting)技术在存储空间和准确率上均有更好的性能体现。

时间序列流的分层段模型

本文工作针对这样一类时间序列流,其特点为:(1)序列动态增长,高维,甚至是无限的;(2)对序列中的数据只能一趟扫描,利用一趟扫描建立时间序列流的近似概要,其后的处理只能依赖该概要结构;(3)对序列中的数据的重视程度由近及远降低,对远的数据逐步遗忘.针对这些特点,本文提出一种称为"分层段模型"的时间序列流通用处理框架.在这一框架下,每一时间序列流将被动态地划分成若干子序列,每个子序列抽取成一个称为"段"的概要结构.段是分层组织的,通过段把传统静态时间序列的主要近似方法应用到时间序列流的场合,并实现流中数据的遗忘机制.所进行的实验验证了该模型的有效性.

分布式流数据频繁项发现算法的研究

对分布式流数据中频繁项的发现算法进行了研究,利用一种新颖的分布式概要算法(DSA)来发现从叶子节点直至根节点的概要结构,通过在不同的分布状态下设置相应的精确梯度来最小化通信负载,并利用真实数据集验证了该结构和算法的有效性。

分布式数据流查询处理的P2P中间件研究

随着Web的大规模应用,分布式数据流的数量迅速增长,其查询处理面临极大的挑战。该文开发了分布式数据流响应查询的P2P中间件原型,利用基于内容路由所提供的可扩展性、通信负载平衡及动态适应性等特性,能有效地处理相似查询,支持内积查询。模拟实验表明该索引机制能减少网络连接的计算资源,提高数据流查询处理效率。

一种有抗体免疫的云模型数据流聚类算法仿真

云模型是云理论的核心,数据流聚类算法在云模型中有较好的应用前景,但也面临着聚类效率、聚类适应性的难题,为此本文提出了一种有抗体免疫的云模型数据流聚类算法。通过设置加权期望值、熵等参数形成云数据特有的数据概要结构,作为抗体代入人工免疫算法中;利用衰减函数和时刻权重来定量表现不同时刻的数据的重要性程度,并以抗体期望克服率为特征值以维持抗体的多样性,采用淘汰法确保最后的数据概要结构更符合云模型数据流的本质特征。实验表明,该算法在云模型数据流中的聚类处理速度和聚类效率均优于传统算法,具有一定的应用价值。

数据挖掘取样方法研究

取样是一种通用有效的近似技术.在数据挖掘研究中,取样方法可显著减小所处理数据集的规模,使得众多数据挖掘算法得以应用到大规模数据集以及数据流数据上.通过对应用于数据挖掘领域的代表性取样方法的比较研究和分析总结,提出了一个取样算法分类框架.在指出了均匀取样局限性的基础上阐述了某些应用场景中选用偏倚取样方法的必要性,综述了取样技术在数据挖掘领域的应用研究与应用发展,最后对数据流挖掘取样方法面临的挑战和发展方向进行了展望.

流数据分析与管理综述

有关流数据分析与管理的研究是目前国际数据库研究领域的一个热点.在过去30多年中,尽管传统数据库技术发展迅速且得到了广泛应用,但是它不能够处理在诸如网络路由、传感器网络、股票分析等应用中所生成的一种新型数据,即流数据.流数据的特点是数据持续到达,且速度快、规模宏大;其研究核心是设计高效的单遍数据集扫描算法,在一个远小于数据规模的内存空间里不断更新一个代表数据集的结构棗概要数据结构,使得在任何时候都能够根据这个结构迅速获得近似查询结果.综述国际上关于流数据的概要数据结构生成与维护的研究成果,并通过列举解决流数据上两个重要问题的各种方案来比较各种算法的特点以及优劣.