PMTree:一种高效的事件流模式匹配方法

被引：8

作者：

程苏珺

王永剑

孟由

程振东

栾钟治

钱德沛

机构：

[1] 北京航空航天大学计算机学院软件开发环境国家重点实验室

[2] 北京航空航天大学计算机学院中德联合软件研究所

[3] 北京航空航天大学北京市网络技术重点实验室

来源：

计算机研究与发展 | 2012年 / 49卷 / 11期

关键词：

事件流; 复杂事件处理; 模式匹配树; NFA; 开销模型;

D O I：

暂无

中图分类号：

TP391.1 [文字信息处理];

学科分类号：

摘要：

复杂事件处理技术从多个持续事件流中分析并提取满足特定模式的事件序列.高吞吐率场景下,如何快速准确地识别事件序列是复杂事件处理技术中一个非常重要的问题.现在事件流的模式匹配方法——NFA、Petri网、有向图等——存在语义描述能力不足、部分算子实现代价高等缺陷.针对这一现状,设计并实现了一种基于树的模式匹配方法——PMTree.PMTree定义了事件模型及相应事件算子,将事件序列映射为树节点,同时将时间窗口约束及谓词约束等放置在相应节点,这些树节点连接成一棵PMTree来支持实时的事件筛选与过滤.进一步研究了PMTree构建过程中的优化策略,并提出了开销模型以及优化构建算法,以尽可能减少模式匹配开销.实验结果表明,相同测试条件下基于PMTree实现的复杂事件处理引擎Cesar吞吐率是基于NFA实现的开源引擎Esper的3～6倍,并且在不同事件量或事件序列复杂度下性能表现稳定.

引用

页码：2481 / 2493

页数：13

共 5 条

[1]

基于复杂事件处理的企业应用与研究[D]. 项立锋.浙江大学. 2010

[2] Design and evaluation of a wide-area event notification service [J].

Carzaniga, A ;

Rosenblum, DS ;

Wolf, AL .

ACM TRANSACTIONS ON COMPUTER SYSTEMS, 2001, 19 (03) :332-383

[3] Implementing ECA rules in an active database [J].

Tan, CW ;

Goh, A .

KNOWLEDGE-BASED SYSTEMS, 1999, 12 (04) :137-144

[4] Active database systems [J].

Paton, NW ;

Díaz, O .

ACM COMPUTING SURVEYS, 1999, 31 (01) :63-103

[5]

A short history of complex event processing .2 Luckharn D. http://www.complexe vents.com/2008/02/15/a-short-history-of-complex-event-processing . 2008

← 1 →