基于有序事件列表的高效复杂事件匹配算法

邱 涛，丁建丽，夏秀峰，郗红梅，谢沛良，周清怡

（1.沈阳航空航天大学 计算机学院，沈阳 110136；2.沈阳飞机工业（集团）有限公司 试飞站/试飞实验室，沈阳 110034）

0 引言

随着射频识别、传感器网络、物联网［1］等技术及应用的快速发展，复杂事件匹配处理已经成为检测、处理、分析和挖掘事件流数据的一种有效手段［2］。复杂事件匹配处理是对满足某些查询模式的一些基本事件进行识别操作，得到能够分析事件发展或其环境变化状态的复杂事件。例如在股票交易信息分析［3］、道路交通规划［4］、数控机床系统［5］和海量航天数据分析［6］等方面都有广泛的应用。

尽管目前已有一些处理方法，例如SASE［7-8］、ZStream［9］、Siddhi［10］等，但这些方法在处理简单查询模式下的事件匹配时存在着一定的局限性。例如SASE 这种将查询转化为自动机模型的方法，由于自动机固定的状态转换使得它处理事件的灵活性受限，无法直接处理带有属性约束条件的否定查询，同时也无法处理并发事件。基于逻辑模型的这种处理方法针对非正式语义对许多真实世界的应用程序构成限制的问题，继而选择采用一种正式的声明性语义，但这种方式并不能处理属性约束上带有量化条件的情形，且基于逻辑的事件识别系统已被先前研究［11］证明效率总体效率偏低。而ZStream 这种基于树型模型的方法，虽然克服了状态难以灵活转换操作的缺陷，但也存在中间结果数量多、大量重复计算、批处理操作漏解等问题。

为了既能满足现有的复杂事件匹配处理的需求，又能进一步提高复杂事件匹配的效率，本文提出了一种利用事件有序列表进行递归遍历的复杂事件匹配方法。首先将来临的事件流数据进行初步的过滤，过滤掉与查询模式不相关事件类型的事件实例，并将相关的事件实例缓存到对应的有序列表当中；再在有序事件列表上执行查询过滤操作，利用递归遍历的方式得到满足查询模式的复杂事件候选序列集合；最后对候选序列进一步做属性验证，最终得到完全满足查询模式的全部复杂事件结果。

综上所述，本文的主要工作如下：

1）提出了一种将事件缓存到有序事件列表上进行复杂事件匹配的方法，将查询模式中的约束条件分解为不同类型，再对不同类型的约束分别设计校验。

2）设计了一种基于递归的ReCEP 算法来确定复杂事件候选序列，能够在时间戳允许范围内，有效地校验是否有对应的一个甚至多个事件实例构成复杂事件候选序列。

3）通过在股票交易模拟数据集上对算法的性能进行实验和分析，验证了所提方法和算法的有效性和高效性。

1 相关工作

随着信息技术的迅猛发展，各类信息系统产生的数据呈指数增长，大规模的数据分析处理在各行各业都得到了广泛的应用。复杂事件匹配作为数据分析处理方式之一，在学术领域已经被广泛地研究。近些年来，对于该问题国内外陆续提出了许多研究方法，这些方法主要可以概括为三类：基于自动机模型、基于逻辑模型和基于树型模型的方法。

目前，基于自动机模型的处理方法是最流行的复杂事件匹配处理方式。这类方法将非确定性自动机作为它的计算模型，把查询模式表示为一系列必须检测的状态，当且仅当转换为最终状态时认为该模式已匹配。例如，SASE、SASE+［12］、Flink CEP［13］、Siddhi、Cayuga［14-15］等都是基于自动机模型的处理方法。SASE 定义了一种用于描述复杂事件需满足的各类约束条件的查询语言，但该方法不支持迭代操作，并且在否定操作上也需要中间大量的无效计算。SASE+在SASE 的基础上支持了闭包操作。Flink CEP 在原理上和SASE 类似，最大的不同在于Flink CEP 没有固定一种语言去定义查询模式，用户需要编写模式，所以有更大的灵活性。Siddhi 是一种商用处理引擎，功能类似于Flink CEP，可以支持代数的所有运算符，但与Flink CEP 相反，Siddhi 提供了一种定义模式的语言。Cayuga 与前面介绍的所有方法不同之处在于Cayuga 没有窗口，把事件看作是持续时间的，它也不支持否定操作。这类基于自动机的方法由于其模型性质导致其具有很多局限性，如匹配事件的顺序必须与状态转换顺序一致。其次，当查询模式中存在否定操作时，自动机难以通过状态转移表达出否定操作。

基于逻辑模型的复杂事件处理系统针对非正式语义对许多真实世界的应用程序构成的限制的问题，采用了基于逻辑的时序表达方式，使用一种正式的声明性语义。记录识别系统（Chronicle Recognition System）［16-17］是一个典型的采用逻辑模型的例子，它是一个纯粹的时间推理系统，输入语言依赖于一种具体化的时间逻辑，其中逻辑规则与具体的时序关系相关联；同时，该系统不支持带有时间变量约束的数学运算符，也不支持事件属性上的量化条件。

基于树型模型的复杂事件匹配方法是近年提出的方法，其以树型的数据结构作为查询匹配的计算模型来处理复杂事件查询。ZStream 是最先提出的基于树型模型的复杂事件匹配方法。它将查询转换为树模型，树的叶子节点存储事件集合，内部节点对应于运算符。这种方法不会对随时到来的数据流进行立即匹配操作，而是等事件达到触发状态时，成批地进行操作。从查询语言角度看，ZStream 所用的树型模型与自动机模型的所表达的查询语义其实是一致的，不同之处在于它的事件匹配顺序不再依赖自动机的状态转移顺序，而是取决于树型结构上选择叶子节点的顺序。此外，E-Cube［18］也是采用树结构的一个复杂事件处理系统，E-Cube的主要功能在于其多查询优化的能力，也就是当匹配的模式共享某些公共结构时，它具有匹配多个模式的能力，同时避免了冗余和重复的计算。相较于基于自动机模型的方法，基于树结构的方法虽然能更好地处理查询中具有层次关系的复杂事件，但需要在每个中间节点上都计算中间结果，从而导致存在大量的重复计算。

2 预备知识与问题定义

复杂事件匹配处理是一种面向事件流的分析技术，对大量来自不同数据源的基本事件执行过滤、关联、聚合等操作，其目标为从大量的基本事件构成的事件流当中，找出满足查询模式语义的更高层次的复杂事件。

定义1事件流。事件流S（s1，s2，…，sn）由一系列的基本事件实例构成。其中si∈S为事件实例，包含了事件的类型（如不同的股票名称）、事件的属性（如股票交易价格等）和事件发生的时间戳等数据信息。

本文使用大写英文字母表示基本事件类型（如事件类型A、事件类型B），事件实例则用相应的小写字母表示（如A的事件实例au、B 的事件实例bv，其中下标表示该有序事件列表上第几个事件实例）。图1所示为一段事件流的示例。图中事件流S包含了A、B、C 三种不同类型的股票价格变化事件，每个事件实例都包含了时间戳与交易价格信息。例如，b1为B事件类型的第1个事件实例，其时间戳为3，交易的价格为706。

图1 事件流示例Fig.1 Example of event stream

复杂事件是由事件流S（s1，s2，…，sn）上的若干基本事件实例构成的一个复合事件，表示为R（r1，r2，…，rm）。复杂事件表示在事件流上发生的客观存在的具体事件，其语义常用查询模式进行表示。

定义2复杂事件查询模式。复杂事件查询模式Q由一组定义在基本事件上的约束条件构成，用以表示客观存在的目标事件的属性特征。

当前的研究工作中已提出多种形式的查询模式用以描述复杂事件［19］，其中SASE 所提出查询模式具有简洁的语法规则，同时具备灵活的表达能力，被广泛使用于诸多复杂事件匹配技术中。本文沿用SASE 中的查询模式定义，其基本结构如下：

PATTERN <目标序列形式>

WHERE <属性约束条件>

WITHIN <时间窗口大小>

RETURN <输出表达形式>

上述查询模式由4 个部分构成：PATTERN 子句定义了查询模式的事件目标序列（E1，E2，…，Eh），其中Ei表示定义在事件类型上的序列操作；WHERE 子句描述了复杂事件中的事件实例在事件属性上需要满足的约束条件；WITHIN 子句限定了该复杂事件在一定的时间间隔内发生；RETURN 子句定义了复杂事件匹配结果的输出表达模式。

事实上，上述查询模式的约束条件来自PATTERN 子句、WHERE 子句与WITHIN 子句。PATTERN 子句约束了目标复杂事件在事件类型序列上的条件，WHERE 子句约束了目标事件需满足的属性条件，WITHIN 子句用时间窗口约束了目标事件发生必须满足的时间范围。

例1 股票交易中的模式查询。用户查询想在众多繁杂的交易数据当中找到想要的交易记录，从而分析股票交易数据。将股票交易市场的交易数据作为事件流，给定的查询模式Q如下所示：

上述查询模式Q中，PATTERN 子句表示关心的股票交易情况，其中发生的事件要满足（A；B；C）的序列形式，即A、B、C 三种类型股票要先后有序的发生。WHERE 子句定义了股票事件实例的股票交易价格属性的约束条件，即A 型股票交易价格在1 000 元以上，A 种股票的交易价格大于B 种股票的y个百分比涨幅后的价格，且A 种股票交易价格低于C 种股票在z个百分比跌幅后的价格。WITHIN 子句限制了该事件发生的时间在10 min 之内。最后要求输出的复杂事件结果以A，B，C 的格式输出所有满足的复杂事件集合。

本文采用的查询模式中PATTERN 子句能够支持3 种序列操作，用以描述不同情况下的事件序列，序列操作的具体描述如下所示：

1）顺序操作（A；B）：表示A 类型的事件实例a发生之后，有B 类型的事件实例b在其后发生，即满足条件a.timestamp

2）否定操作（！A）：否定操作符为“！”，用于表示A 事件类型的事件实例不发生。例如查询模式“A；！B；C”表示C 事件类型的事件实例c跟随在A事件类型的事件实例a之后，即a.timestamp

3）闭包操作（Ak）：表示A 事件类型中的事件实例连续发生至少k次。闭包操作的连续事件实例并不是指实例在事件流上连续出现，而是指在后续类型事件实例到达前闭包操作下的事件实例出现至少k次。例如，对于查询“A；Bk；C”，它要求在实例a与c之间存在至少k个事件实例b。

定义3复杂事件匹配问题定义。给定事件流S和复杂事件查询模式Q，复杂事件匹配即根据查询模式Q中给定的各类约束条件，在事件流S的基本事件实例中匹配出满足所有约束条件的全部复杂事件结果。

复杂事件匹配的处理流程如图2 所示。以查询模式Q和事件流S作为复杂事件处理系统的输入，系统输出即为事件流S中的事件实例组合，这些事件实例必须满足查询Q中的各类约束条件。

图2 复杂事件匹配处理流程Fig.2 Flow of complex event processing

例2 给定图1 所示事件流S与例1 所示的复杂事件查询模式Q，假设Q中的x值设定为1 000，y值为44，z值为49，那么该事件流S（局部片段）将可以匹配到一个满足Q的复杂事件a1，b1，c2。

3 高效的复杂事件匹配方法

本章将介绍本文提出的利用有序事件列表进行递归遍历的复杂事件匹配方法，其基本思想为将查询模式中的约束条件分解为不同类型，再针对不同类型的约束分别设计相应的校验方法。

3.1 复杂事件查询处理框架

本文提出的复杂事件匹配方法包括：事件缓存、查询过滤和属性验证3个步骤，如图3所示。匹配方法的输入为查询模式Q与事件流S，每个步骤都校验了Q中不同部分的约束条件，最后输出的事件序列为满足Q所有约束的匹配结果。

图3 复杂事件匹配处理框架Fig.3 Framework of complex event matching

1）事件缓存：事件流中会包含大量与查询模式不相关的事件实例。例如，例1 中的查询Q仅和事件类型A、B、C 相关，事件流中的其他事件类型（如D、E 等）与Q不相关。事件缓存的目的即利用有序缓冲区将与Q相关的事件实例按照事件类型进行缓存。

2）查询过滤：经过事件缓存处理后，处理系统将得到有序事件列表，即事件实例缓冲区。查询过滤的作用为在事件实例缓冲区上找到满足查询模式Q中PATTERN 子句约束与WITHIN 子句约束的事件实例。例如，对于上文例1 中的查询Q，查询过滤需要在事件流S上找到事件实例序列等。

3）属性验证：通过前面两个步骤获取到的事件实例序列已经满足了查询Q中PATTERN 子句与WITHIN 子句的约束，最后的属性验证步骤则是要进一步校验获取到的候选事件序列是否满足WHERE子句中的约束条件，即属性条件的验证。

3.2 事件缓存

如3.1 节所述，事件缓存的目的是将事件流上的事件实例按照查询模式中的目标序列形式缓存到相对应的有序缓冲区中。给定查询模式Q，PATTERN 目标序列形式为（E1，E2，…，Eh），为目标序列中每个元素Ei对应的事件类型创建相应的缓冲筛选器，进而利用筛选器将事件流上的事件实例缓存到相应的有序缓冲区I（Ei）当中。

WHERE 子句的约束条件可以分为两大类：一类是事件实例属性与常量间的比较条件，本文称为常量约束；另一类是不同事件实例之间的属性比较，称为关联约束。例如，在例1 当中，WHERE 子句的条件a.price >x，由于x为用户给定的常量值，该条件即为一个常量约束。对于条件a.price >b.price，其中a与b均为事件实例，该条件即为一个关联约束。

按照3.1 节步骤将WHERE 子句中的常量约束和关联约束全部都放到属性验证环节进行校验。然而，事实上常量约束仅仅作用于单一的事件类型，事件缓冲筛选器也是作用于单一的事件类型。因此，可以考虑将常量约束的校验放到事件缓存步骤相应的缓冲筛选器中。这种方式会预先筛选掉事件流上不满足这些常量约束的事件实例进入到缓冲区当中，减少了事件缓存与查询过滤步骤产生的中间结果，从而提升查询处理效率。

例3 对于前文所示查询模式Q与事件流S，查询模式Q中包含的目标序列为（A；B；C）。根据该目标序列分别为A、B、C 三种事件类型创建缓冲筛选器，如图4 所示。由于Q中有常量约束a.price>x（假设x取值为1 000），该条件则被添加到A 事件类型的筛选器中。经过该三个筛选器得到相对应的有序事件列表，即缓冲区，分别为I（A）、I（B）与I（C）。I（A）中存储了事件类型为A 的且交易价格属性大于1 000 的事件实例（如a1、a2、a3等，原事件流中的a3由于交易价格属性不满足筛选条件，未被加入缓冲区中）；I（B）与I（C）则分别存储了类型为B 与C 的事件实例。

图4 将事件实例进行过滤并划分到不同有序缓冲区Fig.4 Event instances are filtered and divided into different ordered buffers

3.3 查询过滤

事件流上的事件实例经过事件缓存步骤之后被存储到了相应有序缓冲区中，接下来在有序缓冲区上执行的查询过滤则是复杂事件匹配的核心操作，其作用是匹配出满足复杂事件目标序列形式约束（PATTERN 子句约束）与时间窗口限制（WITHIN 子句约束）的复杂事件候选序列。为了匹配出上述候选序列，本文采用的方法为先从事件缓冲区中确定候选序列的初始事件实例，再设计基于递归的方法从事件缓冲区中匹配出满足条件的复杂事件候选序列。下面分别对上述过程进行详细介绍。

3.3.1 确定初始事件实例

给定相关事件缓冲区，为了从中找到满足约束条件的候选序列，最简单的方式是对缓冲区中的事件实例进行枚举组合，然后再检查组合后的事件序列是否满足了上述约束条件。显然，这种方式会枚举出大量的无效事件序列出来，导致系统匹配效率低。为此，本文采用了一种基于递归的方法从事件缓冲区中找到候选序列。

由于候选序列需满足查询模式中目标序列形式，因此可以通过查询模式的目标序列来确定起始事件E0，并且在该事件对应的缓冲区I（E0）上获取初始事件实例。此时，这些初始事件实例仅是可能存在的候选序列的第一个事件实例，即候选序列的初始事件实例。对于一个初始事件实例ei，当且仅当在剩余的其他类型的有序缓冲区中存在满足时间窗口范围内的事件实例，使得它们能构成的集合满足查询模式目标序列，那么以此ei作为起始的这个事件实例组合则是一个复杂事件候选序列。

本文设计了算法1 来实现上述匹配过程。算法首先找到目标序列中起始事件的有序缓冲区I（E0）（第1）行），并且逐个校验该缓冲区上的事件实例ei（第2）～5）行）。对于每一个事件实例ei，算法为其创建一个集合r，用于存储当前序列已确定了的事件实例（即已满足了Q中目标序列约束的事件实例，ei作为序列中第一个事件实例，r创建时ei已被加入其中）。然后，调用算法MatchSubEvents（见3.3.2 节算法2）来校验在其余事件缓冲区中是否存在时间窗口范围内的事件实例满足了目标序列的约束条件。如果校验成功，则满足的事件实例将作为一个复杂事件候选序列存储到集合R中（第6）行）。

算法1 复杂事件候选序列匹配算法CandCEP。

输入 查询Q中的目标序列Se，事件实例缓存区I，时间窗口大小tw；

输出 匹配的事件序列集合R。

3.3.2 获取候选事件序列

在其他事件有序缓冲区中的验证都可以归结为：在一个时间戳允许范围内，判断缓冲区上是否有对应的事件实例存在。由于构成候选序列的事件实例会存在多个，每个事件实例需利用缓存区判断是否真实存在，本文提出基于递归的方法依次校验剩余的事件实例。

在事件缓冲区上校验满足条件的事件实例的思路为：通过查询模式Q中WITHIN 子句中的时间窗口大小tw来计算出事件实例发生的时间戳范围［tx，ty］，然后在对应事件缓冲区当中判断［tx，ty］时间戳范围内是否存在事件实例。如果构成候选序列的事件实例均存在，则找到的事件实例可以组合为一个复杂事件实例候选序列。

本文设计了基于递归的算法从有序的事件缓冲区中找到候选事件序列，如算法2 所示。

算法2 候选序列匹配算法MatchSubEvents。

输入 事件类型Ej，查询Q中的目标序列Se，匹配的事件序列集合R。

算法2 具有3 个输入参数。Ej表示目标序列上当前已校验成功的事件类型（即对应的事件实例缓冲区上具有满足约束条件的事件实例），Se为查询Q中的目标序列，R用于存储递归校验后得到的复杂事件序列结果。

算法2 先根据Ej得到其后继事件类型Ei（第1）行）。对于Ej.Sr中的存储的每一个集合r（表示当前已经部分满足目标序列约束的事件实例集合），根据r中的事件实例计算出Ei类型的事件实例允许出现的时间戳范围［tx，ty］（第3）行）。由于Ei的序列操作类型不同，在其对应的事件实例缓冲区上进行的校验操作也不同，因此算法2 需分别对Ei的三种序列操作类型进行讨论。

当Ei的序列操作类型为顺序操作时（第4）～8）行），算法在Ei对应的事件缓冲区I（Ei）上找到所有满足时间戳范围［tx，ty］的事件实例ei。由于每一个实例ei的加入，都表示一种新的部分匹配上的目标序列，因此需将ei加入到r中，并创建得到新的集合r'。r'再存入Ei.Sr中，用于下轮递归调用时进行校验。

当Ei的序列操作类型为闭包操作时（第9）～18）行），需先获取闭包参数k值。然后设置一个临时变量count，用于对满足时间戳范围的事件实例进行计数。同理，算法2 需在I(Ei)上找到满足时间戳范围的事件实例。不同于处理顺序操作，仅当实例的个数大于闭包参数值k时，才创建新的集合r'，用于表示新的部分匹配序列。

当Ei的序列操作类型为否定操作时（第19）～22）行），其处理方法不同于顺序操作与闭包操作。复杂事件匹配过程不能包含否定操作下的事件实例，算法2 利用出现在时间戳范围内的实例的时间戳，来更新当前部分匹配集合r的终止时间，从而保证匹配得到的目标序列所在时间戳范围不会包含否定的事件实例。

Ej.Sr中所有集合r都处理完成后，则判断当前处理的Ei是否为查询模式目标序列中最后一个事件类型。如Ei为最后一个事件类型，则当前获得的Ej.Sr中任意一个集合都表示一个满足约束的候选序列，并将其加入到R中（第26）～28）行）；如不是，则算法进行递归调用，直到最后一个事件类型处理完毕（第23）～24）行）。

例4 本例沿用例3 当中股票交易数据缓存到有序缓冲区的数据，由例3 得到的查询模式的起始事件类型A 缓冲区中的起始事件实例为a1：2，将该事件实例放到相应的集合中存储，如图5 中EA.Sr所示。计算其允许后续事件实例时间戳范围为［2，12］，在后续B 事件类型的缓冲区中能匹配到b1：3、b2：8 和b3：9 三个B 类型的事件实例，因此会创建三个新的序列组合存储到集合中，如图5 中EB.Sr所示。相同的，再由当前r中组合b事件实例的时间戳计算出允许其后续c事件实例的时间戳范围，如图中a1：2，b1：3 允许后续时间戳范围为［3，12］，那么在C 事件类型的有序缓冲区当中可以验证到c2：6 和c3：10 两个事件实例，并且创建新的序列组合存储到如图5 的EC.Sr中。同理b2：8 和b3：9 也都能匹配到c3：10 这个事件实例。判断C 事件类型为查询模式中最后一个事件类型时，将当前存储的事件实例集合即复杂事件候选序列输出，如图5 中右侧四个候选序列结果。

图5 查询过滤过程示意图Fig.5 Schematic diagram of query filtering process

3.4 属性验证

由于查询模式WHERE 子句中的关联约束难以在分区缓存的事件缓存和查询过滤中做校验处理，所以在这两个步骤之后得到的复杂事件候选序列并不能保证完全符合查询模式的约束。因此，系统最后一步属性验证的目的是进一步检查查询模式中的关联约束，筛除不满足该约束的候选序列。

针对查询过滤产生的复杂事件候选序列，结果验证步骤则需要在其上添加筛选器，将筛选条件设置为查询模式中的关联约束。复杂事件候选序列通过带有关联约束的筛选器，筛选器检查其上的属性是否均满足设定的关联约束条件，不满足关联约束的候选序列会被筛除掉，满足的即为正确的复杂事件结果。

例5 对于前文给定的查询示例，在经过例4的查询过滤处理之后，得到复杂事件候选序列如图6 中所示，再针对这些复杂事件候选序列添加查询模式中的关联约束作为验证条件，即a.price>（1+y%）*b.price 和a.price<(1-z%)*c.price。图6 中实线框内的a1，b2，c3这一候选序列的a1：2 的交易价格虽然低于c3：10的49%跌幅，但是它并不高于b2：8的44%涨幅，所以它并不是正确的复杂事件结果。最终，得到的四个复杂事件候选序列中有3个复杂事件作为结果被输出。

图6 属性验证过程示意图Fig.6 Schematic diagram of attribute verification process

4 实验测试与结果分析

本章通过实验测试对提出的利用事件缓冲区进行递归遍历的复杂事件匹配方法进行性能分析和评价。实验在基于Java 的原型系统中实现了前面章描述的所有查询评估技术。在本章中展示了本文所提方法和算法的性能研究结果，这些结果可以反映各种因素对性能的影响，并证明了本文方法的有效性和高效性。

4.1 实验设置

为了测试和评价本文所提方法的性能，将本文提出的算法记为ReCEP 算法，并与以下基于自动机模型中目前比较流行的SASE 方法［8］和文献［10］中所提的流处理和复杂的事件处理驱动系统Siddhi方法进行实验对比。

实验数据集采用SASE 股票模拟数据事件流生成器生成的股票交易模拟数据，该数据集包含100万个股票交易数据信息，其中带有时间戳、交易价格、交易数量等属性。在实验过程中，为保证实验的可比性，将复杂事件查询在各个实验中做一致性处理，即相同的目标序列，相同的事件类型个数，相同的属性约束，相同的事件窗口大小。在本章实验中将复杂事件查询匹配结果的处理时间作为实验的性能指标来进行评估。

以下实验所有程序均使用2021.2.2.0 版本的IntelliJ IDEA 编写，JDK 版本为1.8。实验环境为Intel Core i7-10510U@2.5 GHz，8 GB 内存，1 TB 硬盘，Windows 10 64 位操作系统。

4.2 实验分析

在本章实验中，首先将本文提出的ReCEP 算法与SASE、Siddhi 方法在同一查询模式下进行总体性能对比实验，其次又进行了不同影响因素，如复杂事件类型个数、时间窗口大小下各个方法间性能的比较。

实验一 在相同的复杂事件查询模式下，实验一评估了三种方法在处理复杂事件时的总体性能。在该实验中查询序列模式使用三种事件类型即序列为PATTERN（A；B；C），同时给定每组查询相同的属性约束条件，并且设置事件发生2 min内，即WITHIN=120时复杂事件处理的性能。

通过在SASE 股票模拟数据事件流生成器生成的100 万个股票交易模拟数据上进行实验测试，将三种方法对复杂事件处理结果所用的运行时间作为评估指标，发现SASE处理方法运行时间为1 675 ms，Siddhi处理方法运行时间为1 574 ms，而本文提出的ReCEP 算法仅需1 438 ms则可完成复杂事件结果的匹配，ReCEP 算法比SASE 方法的处理时间降低了约14.15%，比Siddhi方法降低了约8.64%。

实验二 改变查询模式中事件类型的长度。实验二评估了查询模式中事件类型的个数对处理性能的影响。在实验二中设置复杂事件查询模式均在同一时间窗口WITHIN=120时，改变查询模式中事件类型个数，分别由2 个递增到6 个事件类型时的5 组评估结果。将三种方法对复杂事件处理结果所用的运行时间作为评估指标，对比实验结果如图7 所示，其中ReCEP 方法比SASE 方法的处理时间降低了约25.63%，比Siddhi方法降低了约18.32%。

图7 查询模式中事件类型的个数对性能的影响Fig.7 Influence of number of event types in query mode on performance

实验三 改变查询模式中时间窗口约束的大小。实验三评估了查询模式中时间约束窗口大小对处理性能的影响。在实验三当中设置查询中的序列模式为固定的三种事件类型顺序操作，即PATTERN（A；B；C），同时给定每组查询相同的属性约束条件，分别测试了时间窗口WITHIN 从60 到300 之间的5 组评估结果。将三种方法对复杂事件处理结果所用的运行时间作为评估指标，对比实验结果如图8 所示，其中ReCEP算法比SASE 方法的处理时间降低了约14.72%，比Siddhi 方法降低了约9.74%。

图8 查询模式中时间约束的大小对性能的影响Fig.8 Influence of size of time constraint in query mode on performance

上述实验结果表明，本文提出的在有序缓冲区上基于递归操作的复杂事件处理方法无论在处理查询模式中事件类型较多或者时间窗口约束较大的情况下，都能够有效得到复杂事件处理结果，并且在处理性能上可以更有效地减少处理时间。

5 结语

本文提出了新型的在有序缓冲区上的复杂事件匹配处理方法，并针对该方法设计了一种基于递归的查询过滤算法ReCEP。根据给定的复杂事件查询模式，通过对事件流进行事件缓存、查询过滤和属性验证的一系列步骤之后，能够正确地求解出所有复杂事件结果。通过利用SASE 提供的模拟真实股票交易数据的事件流生成器，模拟出股票交易数据，针对股票模拟数据集进行实验测试和分析，实验结果表明本文方法能有效进行复杂事件匹配。由于本文只考虑了事件流中事件实例均为正常顺序来临时产生的复杂事件匹配，实际中由于网络延迟等原因数据的来临可能产生乱序的情况，怎样处理事件流中存在乱序的事件实例，将是下一步的研究方向。