[發明專利]一種大規模發布訂閱系統的語義匹配算法

有效

• 申請號: 200810062262.5
• 申請日: 2008-06-17
• 公開（公告）號: CN101295311A
• 公開（公告）日: 2008-10-29
• 發明（設計）人: 尹建偉;呂春旭;李瑩;吳健;鄧水光;吳朝暉
• 申請（專利權）人: 浙江大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 杭州裕陽專利事務所（普通合伙）
• 代理人: 張驍敏

技術領域

本發明涉及Web服務技術領域，尤其是指一種大規模發布訂閱系統的語義匹配算法。

背景技術

發布訂閱是新一代的網絡計算，是一種以大規模、分散控制、動態性、自治性和松耦合為主要特征的分布式計算。已成為分布式計算領域的重要支撐平臺，進入人們的生活、工作、科研等領域，是現代計算和應用的研究熱點。支持復雜網絡的大規模發布/訂閱系統，可以預見的應用場景更是包括面向服務的計算、無線傳感器網絡、移動計算、普適計算、協同環境、企業應用集成等。

如圖1所示，發布/訂閱模型一般由信息生產者(發布者)、信息消費者(訂閱者)和事件通知服務組成。其流程為信息消費者向事件通知服務注冊訂閱，表達對特定信息的興趣；信息生產者以事件形式發送信息到事件通知服務，然后事件通知服務路由匹配的事件到相應的信息消費者。

發布/訂閱系統的核心機制之一就是匹配算法。匹配算法負責高效地找到與給定事件相匹配的所有訂閱條件，其設計目標主要包括：匹配的時間效率、匹配的空間效率和訂閱維護的效率。

數據模型是匹配算法的基礎，不同數據模型的發布/訂閱系統的匹配算法都不一樣。基于Map的發布訂閱系統匹配算法，時間復雜度較低，速度很快，但其空間復雜度為指數級。同時，該算法的訂閱維護的成本很高，每當客戶增加訂閱或取消訂閱時，系統難以對該搜索樹進行修改以反映訂閱的變化，而必須要重建搜索樹?；赬ML的發布/訂閱系統，其表達能力比基于Map的系統有了很大的提高。雖然XML具有很強的表達能力，但是訂閱者必須預先知道被發布的XML文檔所遵從的XML?Schema，才能根據該Schema定義出相應的訂閱條件。

以上發布訂閱系統的事件/訂閱匹配屬于精確匹配，而語義匹配算法是一種支持模糊匹配的方法，即在沒有特定訂閱和發布的精確知識，用戶發布或訂閱采用的是不精確詞匯的情況下，發布和訂閱之間仍然能夠得到有效匹配的算法。

發明內容

針對上述匹配算法的時間效率低、空間復雜度高及維護復雜的問題。本發明提供了一種空間復雜度低，時間復雜度低的大規模發布訂閱系統的語義匹配算法。

一種大規模發布訂閱系統的語義匹配算法，包括如下步驟：

1)為訂閱圖建立索引；

2)轉化事件到特定的數據結構；

3)把事件圖的數據結構提交給事件匹配器；

4)事件匹配器進行事件圖同訂閱圖模式的匹配運算，找出匹配的訂閱，由系統把事件分發給匹配的訂閱者，

其中，所述步驟1)為節點以訂閱總圖的方式保存訂閱，每個訂閱要被合并到訂閱總圖中，過濾不相關的訂閱條件，同時維護訂閱的插入和刪除；

所述步驟2)為直接從事件的原始格式生成事件的數據結構，或先把事件的原始格式轉換成RDF事件圖的結構，然后對圖進行深度或寬度優先搜索遍歷來生成事件的數據結構；

所述步驟4)中事件圖同訂閱圖模式的匹配運算為三個階段：第一個階段根據訂閱索引結構過濾不相關的訂閱；第二個階段根據匹配服務器內核體系結構設置并行方案；第三階段對過濾后的訂閱進行匹配，以發現匹配成功的訂閱。

進一步的，所述RDF事件圖有三類節點：空節點、類型節點和文本節點。

進一步的，所述步驟2)中所述特定的數據結構由包含由屬性和節點對名的PartA和表示資源節點的類型Part?B兩部分組成。

本發明的有益效果為：降低事件與訂閱匹配的時間，提高事件匹配效率，使得隨著訂閱和發布事件數目的增加，事件匹配效率不會受到嚴重的影響，系?統性能不會惡化。同時，根據匹配服務器的內核體系結構自適應調整匹配算法，充分利用多核技術提高匹配效率。