论文部分内容阅读
互联网产业的快速发展在带来数据规模爆炸式增长的同时,也使大数据呈现出越发鲜明的流式特征,数据流以其特有的实时性、突发性、易失性和无限性给传统数据库带来了巨大的挑战。复杂事件处理技术采用事件检测的方法,通过事件属性和事件层次结构之间的关系,使用各种规则处理算法对事件进行匹配和关联,对海量的数据流进行不断的过滤,从中找出满足规则约束条件的事件集合,挖掘出用户感兴趣和有用信息,并提供快速响应。复杂事件处理技术能够满足海量数据处理中高吞吐量、低延迟的需求,是数据流处理的关键技术之一。研究能够适应数据流多样、海量、无限、时变等特性的动态的分析技术及高效的处理算法是数据流实时处理的关键。国内外研究学者相继提出了针对不同应用场景的数据流Top-k复杂事件查询算法。但是,现有研究成果不够完善。这些算法大多对数据流分布和参数变化比较敏感,本论文分别针对数据流动态自适应分区的Top-k连续查询问题、数据流的Top-k支配查询等问题进行了一定的研究和探讨。本文主要的研究工作总结如下:(1)基于动态自适应分区技术的Top-K连续查询算法由于数据流的实时性、持续性、无限性等特点,本文采用滑动窗口技术来处理数据流的连续查询。论文首先采用定长分区策略把窗口分区成多个不相交的子窗口,定长分区方法在维护候选集的时候会造成不必要的维护成本。针对这个问题,进一步提出了动态自适应分区算法,该算法可以根据数据流的动态分布自适应调整分区的大小,并通过曼惠特尼秩和检验检测分区的大小是否合适。然后通过全局过滤和局部过滤方法,提前过滤那些对最终结果集没有贡献的对象,降低通信成本。最后在大量实验的基础上验证了算法的高效性。(2)分布式数据流的Top-k支配查询算法针对传统Top-k查询评分函数不好指定,skyline查询结果集大小不好控制等问题,提出了数据流的Top-k支配查询算法,Top-k支配查询继承了 Top-k查询和skyline查询的优点,因此在决策支持等领域发挥着重要作用。本章采用SparkStreaming+HDFS的分布式查询框架,提出了基于Filter-based的Top-k支配查询算法,并结合subspace skyline和SKYBr技术高效过滤非k-skyband对象,达到提前剪枝的目的,提升了算法的性能。最后通过真实数据集验证了算法在时间和空间方面的性能。