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

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

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

【相似文獻(xiàn)】

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

相關(guān)重要報(bào)紙文章 前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];中國(guó)科學(xué)院研究生院（軟件研究所）;2005年

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

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

5 楊容浩;無(wú)控制DEM匹配算法性能比較與改進(jìn)研究[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è)計(jì)[D];上海交通大學(xué);2015年

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

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

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

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

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

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

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

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

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

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

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

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

本文編號(hào)：2678966