[發明專利]基于謂詞覆蓋的啟發式事件匹配方法

無效

• 申請號: 200910028109.5
• 申請日: 2009-01-09
• 公開（公告）號: CN101551757A
• 公開（公告）日: 2009-10-07
• 發明（設計）人: 潘金貴;張凱隆;莊艷;徐曉旸
• 申請（專利權）人: 南京大學
• 主分類號: G06F9/46
• 分類號: G06F9/46;H04L12/56;H04L29/08
• 代理公司: 南京天翼專利代理有限責任公司
• 代理人: 湯志武;王鵬翔

一、技術領域

本發明涉及內容路由網絡及發布/訂購通信模型中的通訊問題，特別涉及其中的事件匹配方法，涉及具有異步性、動態性、多對多和匿名等特點的發布/訂購通信模型的通訊方式。

二、背景技術

基于內容路由的大規模發布/訂購系統已逐漸成為現今分布式系統通信的研究熱點，在網絡游戲、普適計算、Web?Services、移動計算等領域進行了深入的研究及得到了廣泛的應用。

基于內容路由的發布/訂購通信模型作為一種新型的通信模型，在分布式應用系統通訊中的作用日益明顯，其特點和意義在于它提供了一種松耦合的通訊模式。這種通訊模式有異步通信、動態性、多對多通信方式和可匿名的特點，這些特點使其能夠適應大規模分布式系統的需要。

事件匹配是大規模發布/訂購系統中非常重要的一個實現環節，是決定系統性能的發布事件傳遞效率和準確性的關鍵。

在基于內容路由網絡搭建的發布/訂購系統設計過程中，最受關注的是基于內容的路由的發布/訂購通信模型中的事件匹配效率。在進行事件匹配時，發布事件需要與每個訂購消息進行匹配，而每個發布事件和訂購消息(表達式)又是由多個謂詞組成，所以實際上是通過謂詞之間的匹配來實現發布事件與訂購消息(表達式)的匹配。

當一個系統要處理大量的事件和訂購時，事件匹配需要面對成千上萬的訂購(謂詞)，所以，能否快速高效的進行事件匹配決定了系統的實時性能否得到滿足，同時事件匹配是否準確也將影響整個事件傳遞的準確性，而一個低效率低準確率的事件匹配算法很大程度上會給系統帶來擁塞和瓶頸。

因此，研究一種快速準確的事件匹配算法不僅在相關研究領域具有深遠的意義，同時也在很大程度上是基于內容路由的發布/訂購技術在實際應用領域能否成功應用的關鍵。

現有主要的事件匹配算法研究都是在減少額外的謂詞匹配測試方面進行優化處理，主要的算法一般分為兩類^[1]Walid?Rjaibi，Klaus?Dittrich?and?Dieter?Jaepel.Event?matching?in?symmetricsubscription?systems(對稱訂購系統中的事件匹配)，In?CASCON?Conference，2002：基于謂詞索引算法(Predicate?Indexing?Based)和基于匹配網絡算法(Testing?Network?Based)。

基于謂詞索引算法的事件匹配算法主要以訂購中的謂詞組織成的索引結構為基礎，此類算法一般由兩個階段組成，第一階段進行謂詞匹配測試，第二階段再使用第一階段的測試結果進行訂購匹配測試。代表算法有：計數算法(Counting?Algorithm)^[2]T.W.Yan?andH.Garc’ya-Molina.Index?Structures?for?Selective?Dissemination?of?Information?Under?the?Boolean?Model(在布爾模型下信息選擇性分發的索引結構).ACM?Trans.Database?Syst.，1994，19(2)：pp.332-334；漢森算法(Hanson?Algorithm)^[3]E.Hanson，M.Chaabouni，C.Kim?and?Y.Wang.A?Predicate?Matching?Algorithm?forDatabase?Rule?Systems(一種數據庫規則系統中的謂詞匹配算法)，In?SIGMOD’90，1990等。