基于有序事件列表的高效復雜事件匹配算法

邱 濤，丁建麗，夏秀峰，郗紅梅，謝沛良，周清怡

（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 提供的模擬真實股票交易數據的事件流生成器，模擬出股票交易數據，針對股票模擬數據集進行實驗測試和分析，實驗結果表明本文方法能有效進行復雜事件匹配。由于本文只考慮了事件流中事件實例均為正常順序來臨時產生的復雜事件匹配，實際中由于網絡延遲等原因數據的來臨可能產生亂序的情況，怎樣處理事件流中存在亂序的事件實例，將是下一步的研究方向。