發(fā)布時間：2017-04-08 16:14

  本文關(guān)鍵詞：高效子圖匹配算法研究，，由筆耕文化傳播整理發(fā)布。

【摘要】：圖作為一種數(shù)據(jù)結(jié)構(gòu)能夠簡潔有力地刻畫出普遍事物間的聯(lián)系,因此基于圖的數(shù)據(jù)挖掘與管理技術(shù)無論在學(xué)術(shù)研究還是工業(yè)應(yīng)用上都享有重要的地位。這其中最基本的任務(wù)是如何在圖數(shù)據(jù)集中找到給定的查詢圖,也就是子圖匹配問題。對于正在蓬勃發(fā)展的圖數(shù)據(jù)庫,生物信息學(xué)和社會網(wǎng)絡(luò)分析等領(lǐng)域而言,一個高效的子圖匹配算法的重要性不言而喻。子圖匹配的數(shù)學(xué)基礎(chǔ)是圖論中的經(jīng)典問題子圖同構(gòu),一個著名的NP問題�？上攵�,設(shè)計高效的子圖匹配算法面臨著相當(dāng)巨大大的挑戰(zhàn)。目前,子圖匹配算法的研究工作主要有兩個問題。其一是針對一張邊數(shù)較多的圖如何進行有效的過濾,其二是如何選擇頂點搜索順序來加快子圖同構(gòu)搜索的速度。特別是后者是近年來子圖匹配研究的焦點。針對上述情況,本文提出了一個多段圖模型(MGSM)用于指導(dǎo)頂點搜索順序的選擇。根據(jù)這個模型得到優(yōu)化搜索順序的兩個關(guān)鍵點：特征選擇和代價(導(dǎo)出子圖)估計。其中,第一個關(guān)鍵點與過濾技術(shù)緊密相關(guān),以此出發(fā)可以對以往算法的過濾技術(shù)進行改進。針對第二個關(guān)鍵點,本文提出了一種稱為偽樹估計的的代價估計方法�；谏鲜龉ぷ�,本文設(shè)計了一個精確子圖匹配算法Tps(Three-Phase-Searching)。實驗結(jié)果表明：Tps算法不僅具有顯著的高效性,同時優(yōu)化的頂點搜索順序?qū)D過濾過程和驗證過程同樣有效。另外,本文在對精確與非精確匹配兩個領(lǐng)域的重要算法進行分析的基礎(chǔ)上,提出了一個高效的候選集過濾算法HLMA。實驗證明,該算法既能滿足盡量縮小候選集的過濾要求,又能兼顧過濾的時間效率。本文所描述的工作具有一定的創(chuàng)新性。其中,在與目前公認(rèn)的最快圖匹配算法TurboISO所進行的對比實驗中,Tps算法具有明顯的執(zhí)行效率優(yōu)勢。更重要的是Tps算法的效率優(yōu)勢來自于更合理的理論基礎(chǔ),即本文所提出的MSGM模型可以指出何為最優(yōu)的頂點搜索順序。由此導(dǎo)出的兩大關(guān)鍵點可以從理論上解釋目前若干主要算法的相似相異之處,從而得出與相關(guān)對比試驗結(jié)果相一致的經(jīng)驗結(jié)論。在此基礎(chǔ)上提出的偽樹估計法跳出了前人算法的藩籬,是Tps算法優(yōu)異性能的根基所在�？偠灾�,MSGM模型為子圖搜索算法進一步的研究提供了一個藍圖,而Tps算法是該藍圖下的一個初步嘗試。
【關(guān)鍵詞】：子圖匹配 子圖同構(gòu)搜索 圖挖掘
【學(xué)位授予單位】：北京交通大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2016
【分類號】：O157.5;TP311.13
【目錄】：

• 致謝5-6
• 摘要6-7
• ABSTRACT7-11
• 1 引言11-15
• 1.1 研究背景及意義11-13
• 1.2 本文研究的主要內(nèi)容13-14
• 1.3 論文的組織安排14-15
• 2 子圖匹配理論基礎(chǔ)與研究現(xiàn)狀15-24
• 2.1 子圖匹配問題概述15-16
• 2.2 圖索引技術(shù)的研究進展16-19
• 2.2.1 圖索引的發(fā)展歷程16-17
• 2.2.2 基于子圖特征的圖索引技術(shù)的基本理論17-19
• 2.3 子圖同構(gòu)搜索算法的發(fā)展歷程與理論基礎(chǔ)19-20
• 2.4 子圖匹配問題的最新進展和主要挑戰(zhàn)20-21
• 2.5 非精確匹配問題21-22
• 2.5.1 非精確匹配的研究進展與基本問題21
• 2.5.2 非精確匹配目前的挑戰(zhàn)與成果21-22
• 2.5.3 非精確匹配算法對本文研究的意義22
• 2.6 本章小結(jié)22-24
• 3 基于多段圖模型的高效子圖匹配算法24-45
• 3.1 問題提出24
• 3.2 預(yù)備知識24-30
• 3.2.1 鄰域過濾25-26
• 3.2.2 r-l路徑過濾26-28
• 3.2.3 Ullmann算法和頂點搜索順序28-30
• 3.3 多段圖模型MGSM30-32
• 3.3.1 es特征31-32
• 3.3.2 導(dǎo)出子圖頻率的估計方法32
• 3.4 子圖搜索算法32-36
• 3.4.1 偽樹估計法33-35
• 3.4.2 搜索順序生成35-36
• 3.4.3 Tps算法36
• 3.5 過濾方法的改進36-39
• 3.5.1 索引37-38
• 3.5.2 構(gòu)造生成樹38-39
• 3.6 實驗39-43
• 3.6.1 構(gòu)造實驗數(shù)據(jù)集39
• 3.6.2 過濾階段效率對比39-40
• 3.6.3 驗證階段效率對比40-43
• 3.7 本章小結(jié)43-45
• 4 基于鄰域標(biāo)簽的快速過濾算法45-60
• 4.1 問題提出45
• 4.2 預(yù)備知識45-47
• 4.2.1 標(biāo)簽傳播和h-list46-47
• 4.3 分層頂點過濾47-50
• 4.3.1 路徑向量比對48-49
• 4.3.2 Label向量比對49-50
• 4.3.3 頂點向量比對50
• 4.4 HLMA全局過濾算法50-53
• 4.4.1 候選集生成51-52
• 4.4.2 候選集過濾：匹配度計算52-53
• 4.5 實驗結(jié)果與分析53-59
• 4.5.1 查詢準(zhǔn)確率53-54
• 4.5.2 有效性54-57
• 4.5.3 時間效率57-58
• 4.5.4 與路徑層矩陣的比較58-59
• 4.6 本章小結(jié)59-60
• 5 結(jié)論與展望60-62
• 5.1 本文總結(jié)60
• 5.2 未來展望60-62
• 參考文獻62-65
• 作者簡歷及攻讀碩士學(xué)位期間取得的研究成果65-67
• 學(xué)位論文數(shù)據(jù)集67

【相似文獻】

中國期刊全文數(shù)據(jù)庫 前10條

1 張彩云;康亞男;成汝震;;基于內(nèi)容的發(fā)布/訂閱模型中高效的匹配算法[J];河北師范大學(xué)學(xué)報(自然科學(xué)版);2009年04期

2 趙力;周桑漪;;有關(guān)語音識別的幾種模式快速匹配算法[J];蘇州大學(xué)學(xué)報(自然科學(xué));1991年03期

3 陳昊;李瓊;趙紹東;;一種新的快速地磁匹配算法[J];傳感器與微系統(tǒng);2011年12期

4 李峰,周源華;基于內(nèi)容的匹配算法[J];紅外與毫米波學(xué)報;2000年01期

5 童余德;邊少鋒;蔣東方;向才炳;;一種新的基于局部重力圖逼近的組合匹配算法[J];地球物理學(xué)報;2012年09期

6 譚志國;孫即祥;滕書華;;基于KL變換的點匹配[J];自然科學(xué)進展;2007年07期

7 章思亮;臧德彥;;基于轉(zhuǎn)向角函數(shù)的形狀匹配算法[J];科技廣場;2009年01期

8 陳志楚;;一種基于k鄰域算法的指紋匹配算法研究[J];赤峰學(xué)院學(xué)報(自然科學(xué)版);2012年19期

9 鮑文霞;梁棟;唐俊;;一種基于譜相關(guān)性的概率松弛匹配算法[J];光學(xué)學(xué)報;2010年03期

10 顏普;梁棟;王葵;;一種基于圈基的譜匹配算法[J];安徽大學(xué)學(xué)報(自然科學(xué)版);2012年05期

中國重要會議論文全文數(shù)據(jù)庫 前10條

1 王翠茹;高麗鮮;;發(fā)布訂閱系統(tǒng)中匹配算法的研究[A];全國第20屆計算機技術(shù)與應(yīng)用學(xué)術(shù)會議（CACIS·2009）暨全國第1屆安全關(guān)鍵技術(shù)與應(yīng)用學(xué)術(shù)會議論文集（上冊）[C];2009年

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

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

4 姚辰松;魯昌華;;指紋匹配算法的研究[A];全國第19屆計算機技術(shù)與應(yīng)用（CACIS）學(xué)術(shù)會議論文集（上冊）[C];2008年

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

6 龔才春;黃玉蘭;許洪波;白碩;;基于多重索引模型的大規(guī)模詞典近似匹配算法[A];第三屆全國信息檢索與內(nèi)容安全學(xué)術(shù)會議論文集[C];2007年

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

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

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

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

中國博士學(xué)位論文全文數(shù)據(jù)庫 前3條

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

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

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

中國碩士學(xué)位論文全文數(shù)據(jù)庫 前10條

1 劉芳萍;基于特征匹配的雙目立體圖像深度提取算法研究[D];上海師范大學(xué);2015年

2 楊騰飛;SIFT匹配算法在遙感影像平面精度評定中的應(yīng)用[D];昆明理工大學(xué);2015年

3 劉強;多源信息融合框架下輔助導(dǎo)航系統(tǒng)的景象匹配算法研究[D];上海交通大學(xué);2015年

4 鐘佩;基于ACS的高階圖匹配算法研究[D];西安電子科技大學(xué);2014年

5 楊揚;面向Web規(guī)模圖數(shù)據(jù)的子圖匹配算法的研究與實現(xiàn)[D];東北大學(xué);2013年

6 張宏利;云服務(wù)中任務(wù)分解與匹配算法研究[D];西安工業(yè)大學(xué);2013年

7 郜方方;基于內(nèi)容的發(fā)布訂閱系統(tǒng)中匹配問題的關(guān)鍵技術(shù)研究[D];河南大學(xué);2015年

8 戴昕;高效子圖匹配算法研究[D];北京交通大學(xué);2016年

9 來瑾穎;面向發(fā)布/訂閱的自動化訂閱分解模型與匹配算法研究[D];浙江大學(xué);2010年

10 劉香麗;指紋識別中匹配算法的研究[D];湖南大學(xué);2011年

  本文關(guān)鍵詞：高效子圖匹配算法研究，由筆耕文化傳播整理發(fā)布。

本文編號：293215