機(jī)器學(xué)習(xí)論文-基于本體的發(fā)布_訂閱系統(tǒng)的數(shù)據(jù)模型和匹配算法-資料下載頁
2025-06-06 05:10本頁面
【正文】 4p 3p 2r d f : t y p er d f : t y p er d f : t y p er d f : t y p e_ : H ,? 1 , E M S ( 5 ) _ : H ,? 3 , E M S ( 6 )_ : a ,? 2 , E M S ( 1 ) _ : a ,? 4 , E M S ( 2 ) _ : c ,? 4 , E M S ( 4 )_ : b ,? 4 , E M S ( 3 )_ : H = _ : H_ : H = _ : H? 1 = _ : a_ : H = _ : H? 3 = _ : c_ : H = _ : H? 1 = _ : a? 2 = _ : b_ : H = _ : H? 1 = _ : a? 4 = _ : c_ : H = _ : H? 1 = _ : a? 4 = _ : d_ : H = _ : H? 3 = _ : c? 4 = _ : d_ : H = _ : H? 1 = _ : a? 2 = _ : b? 4 = _ : d (a) An event graph (a) 事件圖 (b) The corresponding matching tree (b) 對(duì)應(yīng)的匹配樹 已通過 SBPV 檢驗(yàn) ,unchecked 表示尚未完成檢驗(yàn) .初始時(shí) ,各結(jié)點(diǎn)的狀態(tài)均為 unchecked.對(duì)于方框結(jié)點(diǎn) ,只要它有一個(gè)孩子的狀態(tài)變?yōu)?checked,其狀態(tài)就變?yōu)? ,當(dāng)其所有孩子的狀態(tài)都為 checked 時(shí) ,其狀態(tài)才變?yōu)?checked. 每個(gè)圓圈結(jié)點(diǎn)中有一個(gè) unCheckedChildren 字段 ,表示它所擁有的狀態(tài)為 unchecked 的孩子總數(shù) . 在匹配樹的創(chuàng)建過程中 ,當(dāng)某個(gè)圓圈結(jié)點(diǎn)不能派生出新的 語句模式 時(shí) ,系統(tǒng)將對(duì)匹配樹進(jìn)行回溯 ,以調(diào)整其上層結(jié)點(diǎn)的狀態(tài) .其步驟如下 : 1) 將當(dāng)前結(jié)點(diǎn)的狀態(tài)置為 checked. 2) 如果本結(jié)點(diǎn)為圓圈結(jié)點(diǎn) : a) 若它是根結(jié)點(diǎn) ,則回溯過程結(jié)束 . b) 若它不是根結(jié)點(diǎn) ,檢查父結(jié)點(diǎn)的狀態(tài)是否為 ,回溯過程結(jié)束 .若不是 ,則將父結(jié)點(diǎn)作為當(dāng)前結(jié)點(diǎn) ,遞歸調(diào)用本回溯過 程 . 3) 如果本結(jié)點(diǎn)為方框結(jié)點(diǎn) ,則將父結(jié)點(diǎn)的 unCheckedChildren減 0,則置父結(jié)點(diǎn)為當(dāng)前結(jié)點(diǎn) ,遞歸調(diào)用本回溯過程 ,否則回溯過程結(jié)束 . 當(dāng) SBPV 檢查完成以后 ,如果匹配樹的根結(jié)點(diǎn)的狀態(tài)為 unchecked,則表示匹配失敗 .由于SBPV 檢查可以在匹配樹的創(chuàng)建時(shí)同步完成 ,所以當(dāng)系統(tǒng)對(duì)事件內(nèi)容遍歷完成之后 ,只需對(duì)那些根結(jié)點(diǎn)狀態(tài)為 checked 的匹配樹進(jìn)行 BEBV檢查 ,從而可以大大提高處理的效率 . 算法分析 令 TS 表示平均每個(gè)事件中的帶類型語句個(gè)數(shù) ,D 表示 EMS 數(shù)組中平均每個(gè) 元語句 所能推導(dǎo)的 元語句 個(gè)數(shù) ,W 表示平均每個(gè)待匹配項(xiàng)鏈表中的結(jié)點(diǎn)數(shù) ,SP 表示各匹配樹中平均每個(gè)圓圈結(jié)點(diǎn)下的 語句模式 個(gè)數(shù) ,則由算法中的循環(huán)層次可知 ,本算法的時(shí)間復(fù)雜度為 O(TS?D?W?SP).一般來說 ,TS,D,SP的值都比較小 ,且不受訂閱數(shù)量的影響 ,而 W的值則可能會(huì)隨著訂閱數(shù)量的增加而增加 . 設(shè)系統(tǒng)中的訂閱數(shù)量為 n,EMS 數(shù)組中 元語句 數(shù)量為 m,平均每個(gè)匹配樹中的 語句模式 數(shù)量為 sp,則 W?(n?sp)? ,本算法的時(shí)間復(fù)雜度與訂閱數(shù)量呈線性關(guān)系 . 在空間復(fù)雜度方面 ,本算法的空間占用主要包括以下兩個(gè)方面 : (1) 各訂閱條件 所對(duì)應(yīng)的匹配樹 .匹配樹中的結(jié)點(diǎn)個(gè)數(shù)由訂閱圖和事件圖決定 ,與訂閱條件數(shù)量無關(guān) . (2) EMS 數(shù)組 (不包括其中的 待匹配項(xiàng) 鏈表 ,因?yàn)樵撴湵碇械慕Y(jié)點(diǎn)同時(shí)也在匹配樹中 ).其大小由事件的概念模型決定 . 設(shè)匹配樹的平均大小為 mt,EMS 數(shù)組中每一項(xiàng)的空間占用為 e(不包括其中的 待匹配項(xiàng) 鏈表 ),則本算法的空間復(fù)雜度為 O(n?mt+m?e).因此 ,總的來說 ,本算法的空間復(fù)雜度與訂閱數(shù)量呈線性關(guān)系 . 5 結(jié) 論 我們將語義 Web 技術(shù)與發(fā)布 /訂閱技術(shù)結(jié)合起來 ,提出了一種新型的發(fā)布 /訂閱系統(tǒng) .該系統(tǒng)能夠利用事件的語義知識(shí) ,提供更為準(zhǔn)確的匹配 ,同時(shí)能夠支持具有復(fù)雜數(shù)據(jù)結(jié)構(gòu) (如圖狀結(jié)構(gòu) )的事件 . 在本系統(tǒng)中 ,事件概念模型是用 DAML+OIL 語言來描述的 .該語言具有較強(qiáng)的描述能力 ,能夠?qū)︻惡蛯傩赃M(jìn)行多種語義約束 ,而本系統(tǒng)只利用了其描述能力的一小部分 .我們下一步的工作將是進(jìn)一步改進(jìn)本系統(tǒng)的概念模型 ,使其能夠包含更為豐富的語義知識(shí) ,以進(jìn)一步提高訂閱匹配的準(zhǔn)確度和效率 . 參考文獻(xiàn)： [1].Efficient Filtering and Routing in a Scalable XMLBased PublishSubscribe. [2].Efficient filtering of XML documents for selective dissemination of information [3].Highperformance XML filtering： An overview of YFilter [4].Path sharing and predicate evaluation for highperformance XML filtering [5].SCRIBE： The design of a largescale event notification infrastructure [6].Spidercast： a scalable interestaware overlay for topicbased pub sub munication [7].Towards an interscale XML dissemination service [8].XPath queries on streaming data [9].Yfilter： Efficient and scalable filtering of XML documents [10].Forwarding in a ContentBased Network [11].The Eighth IEEE Workshop on Hot Topics in Operating Systems [12].XTreeNet： Scalable overlay works for XML content dissemination and querying (synopsis) [13].Implementing a scalable XML publish subscribe system using relational database systems [14].On efficient matching of streaming XML documents and queries [15].WebFilter： A highthroughput XMLbased publish and subscribe system [16].SCRIBE： A largescale and decentralized applicationlevel multicast infrastructure [17].Bayeux： An architecture for scalable and faulttolerant widearea data dissemination
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號(hào)-1