發(fā)布時間：2020-05-24 20:44

【摘要】：近年來,隨著Internet的飛速發(fā)展,分布式計算的應(yīng)用范圍越來越廣、使用規(guī)模越來越大。在當(dāng)下,基于分布式計算的信息發(fā)布系統(tǒng)得到廣泛的應(yīng)用。傳統(tǒng)的信息發(fā)布系統(tǒng)具有高耦合的特點,很難適用于大規(guī)模、異步、多點通訊的需要。而發(fā)布/訂閱系統(tǒng)由于其自身具有異步、多點通訊的特點,能夠很好的應(yīng)用到大型互聯(lián)網(wǎng)信息發(fā)布/訂閱系統(tǒng)低耦合通訊的需求。發(fā)布/訂閱系統(tǒng)可分為基于主題、渠道和基于內(nèi)容的發(fā)布/訂閱系統(tǒng),其中基于主題和基于渠道的發(fā)布/訂閱系統(tǒng)雖然實現(xiàn)簡單,但其表達能力有限,不適用于大規(guī)模的分布式系統(tǒng)中;而基于內(nèi)容的發(fā)布/訂閱系統(tǒng)具有豐富的表達能力、訂閱較為靈活,并能對事件進行檢索,更適合應(yīng)用于大規(guī)模的分布式系統(tǒng)中。在基于內(nèi)容的發(fā)布/訂閱系統(tǒng)中,系統(tǒng)的訂閱需要將事件與訂閱條件進行匹配,且系統(tǒng)會根據(jù)匹配的結(jié)果把數(shù)據(jù)轉(zhuǎn)發(fā)給訂閱者,當(dāng)訂閱的數(shù)量非常大的時候,系統(tǒng)中存在大量的事件和訂閱,有可能導(dǎo)致系統(tǒng)大量的阻塞。匹配算法的目的,是負(fù)責(zé)發(fā)布/訂閱系統(tǒng)能夠高效的、可靠的找到給定事件相匹配的訂閱,因此,如何實現(xiàn)一個高效的匹配算法,并構(gòu)建一個適應(yīng)于大規(guī)模發(fā)布者和訂閱者并行交互的高效發(fā)布/訂閱系統(tǒng),是目前國內(nèi)外學(xué)者研究的重點。目前大多數(shù)系統(tǒng)中所采用的方法是通過樹形結(jié)構(gòu)對訂閱條件建立索引,從而提高了匹配效率,但仍存在匹配時間消耗過大、重復(fù)匹配等問題。針對這些問題,本文通過在現(xiàn)有算法基礎(chǔ)上進行改進,提出了基于多層約束搜索樹的匹配算法,在此基礎(chǔ)上,結(jié)合倒排索引,構(gòu)建了適應(yīng)于大規(guī)模發(fā)布者和訂閱者并行交互的高效匹配方案,主要研究工作如下:1、設(shè)計了多層約束搜索樹的快速匹配算法—MCTF�；�于約束搜索樹的算法,雖然相同條件只需匹配一次,但訂閱條件與事件匹配時需要遍歷整棵搜索樹,系統(tǒng)開銷仍然較大。針對這樣的問題,設(shè)計了多層約束搜索樹快速匹配算法—MCTF,MCTF通過增加多層約束條件和建立約束之間的覆蓋關(guān)系,在匹配時當(dāng)訂閱條件滿足約束條件時,遍歷即終止,不再繼續(xù)遍歷整顆約束搜索樹,從而提高了匹配效率,降低了維護開銷。實驗表明MCTF匹配消耗時間得到了明顯的降低。2、設(shè)計了基于倒排索引的pub/sub系統(tǒng)的匹配機制—IFMA。多層約束搜索樹快速匹配算法MCTF,當(dāng)一個事件對多個訂閱條件時,通過約束覆蓋減少了重復(fù)匹配;但在多個事件對多個訂閱條件時,仍存在較多重復(fù)匹配問題。為了解決這個問題,通過在多層約束搜索樹基礎(chǔ)上引入倒排索引,構(gòu)建了適應(yīng)于大規(guī)模發(fā)布者和訂閱者并行交互的高效匹配機制—IFMA,通過倒排索引解析訂閱條件和事件間的覆蓋關(guān)系,減少了訂閱條件和事件的匹配次數(shù),進一步提高了匹配效率。
【圖文】：

2.1.1 概念為了更好的了解發(fā)布/訂閱系統(tǒng)，，如圖 2-1，顯示了一個典型的發(fā)布/訂閱系統(tǒng)。發(fā)布系統(tǒng)是一個信息交互的中間件系統(tǒng)，將信息的生產(chǎn)者和系統(tǒng)的消費者關(guān)聯(lián)在一起，信息的生產(chǎn)者稱為發(fā)布者(publisher)，信息的發(fā)布者稱為訂閱者(subscriber)，發(fā)布負(fù)責(zé)把信息傳遞給消息中間件，訂閱者只負(fù)責(zé)向中間件訂閱自己感興趣的信息，如費者不感興趣，也可以取消事件訂閱。信息具體的發(fā)布和傳遞則由發(fā)布/訂閱系統(tǒng)負(fù)其中匹配算法(matcher)是能夠準(zhǔn)確的找到訂閱者事件與發(fā)布者事件進行快速的匹配種算法。

所有匹配了的謂詞放入到集合 satisfied-preds（初始狀態(tài)為空 satisfied-preds 中的謂詞集合，判斷 e 使 S 中哪些訂閱滿足條件ity=kaifeng) and (temperature<30) 滿 足 時 ， 那 么 S=(Cityure<40)必定滿足。后面的謂詞就不用在進行判斷。如圖 2-2 所示
【學(xué)位授予單位】：河南大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2018
【分類號】：TP301.6

【相似文獻】

相關(guān)期刊論文 前10條

1 張莉;李甫;吳開騰;;無方向的三角形匹配指紋識別[J];中國圖象圖形學(xué)報;2017年09期

2 萬莛;;最大匹配算法研究[J];微型機與應(yīng)用;2012年08期

3 唐俊;趙曉娟;;一種用于入侵檢測系統(tǒng)的可變r匹配算法[J];計算機應(yīng)用研究;2010年02期

4 劉思含;賈美娟;;樹匹配算法在網(wǎng)頁分類中的應(yīng)用[J];電腦學(xué)習(xí);2010年04期

5 耿慶宦;呂良雙;;產(chǎn)生式系統(tǒng)規(guī)則匹配算法研究[J];計算機與現(xiàn)代化;2009年11期

6 何偉方;;DP動態(tài)匹配算法實現(xiàn)語音的實時識別[J];浙江絲綢工學(xué)院學(xué)報;1987年02期

7 徐志才;最大權(quán)匹配算法的改進與實現(xiàn)[J];電子科學(xué)學(xué)刊;1988年04期

8 涂國防;徐佩霞;;運動補償圖象編碼中的Block自適應(yīng)匹配算法[J];遙測遙控;1988年06期

9 姜勤;潘士光;;一種松弛標(biāo)記體視匹配算法[J];信號處理;1988年04期

10 何偉方,青木由直;DP動態(tài)匹配算法實現(xiàn)語音的實時識別[J];數(shù)據(jù)采集與處理;1989年01期

相關(guān)會議論文 前10條

1 杜云峰;許娜;孫爽;許立永;董彥榮;;一種基于排除的串匹配算法[A];2007北京地區(qū)高校研究生學(xué)術(shù)交流會通信與信息技術(shù)會議論文集（上冊）[C];2008年

2 李曉雷;黃新生;王亦平;徐婉瑩;;穩(wěn)健快速的匹配算法研究[A];'2008系統(tǒng)仿真技術(shù)及其應(yīng)用學(xué)術(shù)會議論文集[C];2008年

3 吉大純;李學(xué)軍;侯金寶;;基于坡的時間規(guī)整快速影像匹配算法[A];圖像圖形技術(shù)研究與應(yīng)用(2010)[C];2010年

4 姚益平;盧錫城;;基于移動相交信息的動態(tài)區(qū)域匹配算法[A];仿真計算機與軟件、仿真方法與建模學(xué)術(shù)交流會論文集[C];2004年

5 郭莉;劉燕兵;譚建龍;;基于存儲壓縮的多模式串匹配算法[A];全國第八屆計算語言學(xué)聯(lián)合學(xué)術(shù)會議（JSCL-2005）論文集[C];2005年

6 楊靚;黃巾;盧強;黃士坦;;基于全息相關(guān)系數(shù)矩陣的匹配算法[A];第十一屆全國信號處理學(xué)術(shù)年會（CCSP-2003）論文集[C];2003年

7 宣琦;吳鐵軍;;復(fù)雜網(wǎng)絡(luò)間節(jié)點匹配算法研究[A];2009年第五屆全國網(wǎng)絡(luò)科學(xué)論壇論文集[C];2009年

8 林雪娥;楊鑒;熊艷嬌;劉懷憬;李詩心;胡湘興;;基于拼寫規(guī)則和最大匹配算法的泰語分詞[A];需將論文集名稱修改為“第十二屆全國人機語音通訊學(xué)術(shù)會議（NCMMSC2013）論文集[C];2013年

9 鄭凱;宮學(xué)慶;閆鶯;周紅福;周傲英;;基于噪聲數(shù)據(jù)流的高效相似匹配算法[A];第二十四屆中國數(shù)據(jù)庫學(xué)術(shù)會議論文集（研究報告篇）[C];2007年

10 徐寶昌;陳哲;;基于神經(jīng)網(wǎng)絡(luò)的景像匹配算法研究[A];中國慣性技術(shù)學(xué)會第五屆學(xué)術(shù)年會論文集[C];2003年

相關(guān)重要報紙文章 前1條

1 義川;Web 3.0更有前途？[N];網(wǎng)絡(luò)世界;2006年

相關(guān)博士學(xué)位論文 前10條

1 韓雨蓉;水下導(dǎo)航重力匹配算法研究[D];北京理工大學(xué);2017年

2 汪錦嶺;面向Internet的發(fā)布/訂閱系統(tǒng)的關(guān)鍵技術(shù)研究[D];中國科學(xué)院研究生院（軟件研究所）;2005年

3 錢詩友;大規(guī)模發(fā)布/訂閱系統(tǒng)匹配算法研究[D];上海交通大學(xué);2015年

4 楊天龍;面向網(wǎng)絡(luò)入侵檢測的串匹配算法優(yōu)化[D];哈爾濱工業(yè)大學(xué);2014年

5 楊容浩;無控制DEM匹配算法性能比較與改進研究[D];西南交通大學(xué);2012年

6 郭克華;基于微分幾何的局部相似目標(biāo)匹配算法研究[D];南京理工大學(xué);2008年

7 羅楠;圖像局部不變特征的匹配算法及應(yīng)用研究[D];南京理工大學(xué);2015年

8 張樹壯;面向網(wǎng)絡(luò)安全的高性能特征匹配技術(shù)研究[D];哈爾濱工業(yè)大學(xué);2011年

9 嚴(yán)駿馳;圖匹配問題的研究和算法設(shè)計[D];上海交通大學(xué);2015年

10 張步陽;半導(dǎo)體芯片封裝過程中視覺定位關(guān)鍵技術(shù)研究[D];華中科技大學(xué);2016年

相關(guān)碩士學(xué)位論文 前10條

1 李秉宸;支持交換的近似串匹配算法的研究與實現(xiàn)[D];吉林大學(xué);2019年

2 馬曉珂;基于非線性尺度空間的圖像特征提取與匹配算法研究[D];河南大學(xué);2019年

3 萬季;個性化車輛合乘服務(wù)研究[D];鄭州大學(xué);2019年

4 吳棟;基于機器學(xué)習(xí)的多任務(wù)多設(shè)備匹配算法研究[D];浙江大學(xué);2019年

5 孫琢;多模式車位預(yù)約實時匹配算法研究[D];北京郵電大學(xué);2019年

6 楊光;基于FPGA的主動式雙目匹配算法研究[D];北京郵電大學(xué);2019年

7 章亞書;不規(guī)則邊緣圖形的快速拼接匹配算法研究[D];哈爾濱理工大學(xué);2019年

8 許文;面向大規(guī)模圖數(shù)據(jù)的分布式子圖匹配算法研究[D];中北大學(xué);2019年

9 吳曉聲;出租車動態(tài)共乘匹配優(yōu)化算法研究[D];長安大學(xué);2018年

10 孔祥雯;面向移動終端的部分指紋匹配算法研究與實現(xiàn)[D];山東大學(xué);2018年

本文編號：2678966