面向实时监控应用的事件流相似性分析技术的研究

论文摘要

事件流作为数据库领域的新兴热点问题,近年来获得了日益广泛的关注。很多应用在本质上都是事件驱动的,例如,RFID采集到的元数据可以看做是一种简单事件,商业事务处理中每次交易事务或数据变化也可以作为事件,此外还包括网络报警事件监测、传感器网络监测等等。在面向实时监控的应用中,这些连续到达的事件形成了语义丰富的无界事件流。事件流是实时流数据的一种特殊形式,由于其具有无限性、瞬时性、有序性、时效性和语义丰富性等特点,传统的数据管理技术无法应对事件流管理中出现的挑战,需要探索新的技术与方法。为了从实时到达的事件流的海量事件中探测复杂事件、发现频繁模式以及进行异常事件检测等等,都需要对多维事件流之间的关系进行分析。事件流相似性探测技术是达到上述目标的重要手段,同时也是实时事件流管理的核心问题之一,具有重要的科研意义和商业价值。本文针对该问题进行了深入研究,主要工作如下：1)首先提出了事件流相似性的定义,采用带权重的编辑距离方法来度量相似度,利用动态规划方法进行计算。该度量能够较好地反映出事件流的相似程度。2)由于采用传统的编辑距离方法计算相似度具有较高的时间复杂度,难以满足面向实时监控应用的事件流的时效性,因此提出一种基于共现度的方法对以滑动窗口整体为单位的事件流进行相似性分析。该方法利用计算简单的共现度,从多个事件流中迅速过滤掉不符合条件的事件流,从而减小候选集的大小,加快相似性分析的速度。3)针对事件流的流特性,采用滑动窗口模型；同时提出一种高效的增量维护机制,最大可能地利用已有计算结果,在不影响精度的前提下提高处理速度。4)针对事件流相似区域位置随机及长度随机的特点,在固定窗口下进行相似性分析会漏掉部分相似结果,因此在窗口整体不相似的情况下进行面向局部特征的相似性查找,并给出局部相似区域的起止位置。实验和分析证明,本文提出的事件流相似性分析方法具有理论上的可行性和操作上的高效与正确性。

论文目录

• 摘要
• Abstract
• 第1章 引言
• 1.1 事件流管理概述
• 1.1.1 事件流简介
• 1.1.2 事件流特点及应用
• 1.1.3 事件流管理技术
• 1.1.4 事件流管理系统
• 1.2 问题提出
• 1.3 本文贡献
• 1.4 组织结构
• 第2章 相似性分析研究现状
• 2.1 时间序列相似性分析技术
• 2.1.1 时间序列的模式表示
• 2.1.2 时间序列相似性分析
• 2.1.3 时间序列相似性度量
• 2.2 事件序列相似性分析技术
• 2.2.1 事件序列相似性分析
• 2.2.2 事件序列属性相似性分析
• 2.2.3 事件相似性
• 2.3 本章小结
• 第3章 事件流建模
• 3.1 事件流建模
• 3.1.1 事件建模
• 3.1.2 事件流定义
• 3.1.3 事件流的高层抽象
• 3.2 事件流片段模型
• 3.3 共现度定义
• 3.4 本章小结
• 第4章 基于共现度的事件流相似性分析
• 4.1 事件流相似性分析
• 4.1.1 问题描述
• 4.1.2 事件流相似性度量
• 4.1.3 理论分析
• 4.2 基于共现度的高效事件流相似性分析
• 4.2.1 共现度性质
• 4.2.2 基于共现度的事件流相似性分析方法
• 4.2.3 共现度闽值设置
• 4.3 事件流相似性分析的增量维护
• 4.3.1 滑动窗口增量维护算法
• 4.3.2 算法复杂度分析
• 4.4 实验评估
• 4.4.1 实验设置
• 4.4.2 实验结果
• 4.5 本章小结
• 第5章 面向局部特征的事件流相似性分析
• 5.1 问题描述
• 5.2 面向局部特征的事件流相似性分析
• 5.2.1 基本定义
• 5.2.2 基于共现系数的相似区间查找
• 5.3 局部特征相似的增量维护
• 5.4 实验验证
• 5.4.1 实验设置
• 5.4.2 实验结果
• 5.5 本章小结
• 第6章 结论
• 6.1 总结
• 6.2 未来工作
• 参考文献
• 致谢
• 攻读硕士学位期间的论文项目情况