本文關(guān)鍵詞：基于容忍度K的子圖查詢(xún)匹配方法研究

  更多相關(guān)文章： 圖 近似子圖 容忍度 索引 子圖匹配

【摘要】：圖是計(jì)算機(jī)科學(xué)中常見(jiàn)的數(shù)據(jù)結(jié)構(gòu),生活中實(shí)體與實(shí)體之間的關(guān)系錯(cuò)綜復(fù)雜、聯(lián)系緊密,因此圖在眾多復(fù)雜數(shù)據(jù)建模中廣泛應(yīng)用,在匹配復(fù)雜數(shù)據(jù)關(guān)系的過(guò)程中也扮演著越來(lái)越重要的角色,如何對(duì)圖進(jìn)行有效查詢(xún)和匹配成為近些年的研究熱點(diǎn)。在已提出的子圖匹配方法中,首先過(guò)濾掉不滿(mǎn)足匹配條件的節(jié)點(diǎn),然后再進(jìn)行邊和圖的匹配,這稱(chēng)為基于節(jié)點(diǎn)的方法。然而這種方法僅僅使用節(jié)點(diǎn)信息過(guò)濾掉不滿(mǎn)足匹配條件的元素,圖的邊涵蓋大量的信息卻沒(méi)有效利用。近似子圖是指不缺失查詢(xún)圖的任何節(jié)點(diǎn),而只丟失一定數(shù)量的邊,而邊丟失的數(shù)量處在一定范圍內(nèi),這個(gè)閾值稱(chēng)為容忍度K。噪聲因素使圖的邊信息丟失變得常見(jiàn),即便在邊缺失的情形下,也要找到查詢(xún)圖的近似匹配子圖以備研究和分析。因此,本文提出了圖的基于邊的近似子圖匹配方法。首先,提出圖的邊標(biāo)簽索引,它能實(shí)現(xiàn)對(duì)圖的高效過(guò)濾和查詢(xún)。充分利用邊的索引信息,在查詢(xún)檢索階段不僅能過(guò)濾掉不合格(不匹配)的節(jié)點(diǎn)和邊,也避免了匹配階段進(jìn)行不必要的節(jié)點(diǎn)、邊連通性檢測(cè),從而減少了算法的冗余匹配步驟。其次,對(duì)給定的查詢(xún)圖進(jìn)行預(yù)處理,生成查詢(xún)圖的近似子圖查詢(xún)邊序和精確子圖查詢(xún)邊序進(jìn)行查詢(xún)和匹配。最后,引入改進(jìn)的位串向量數(shù)據(jù)結(jié)構(gòu),對(duì)被查詢(xún)圖的子圖進(jìn)行子圖匹配驗(yàn)證和連通性檢測(cè),從而提高圖的子圖匹配效率,減少冗余的子圖匹配步驟。在真實(shí)數(shù)據(jù)集和合成數(shù)據(jù)集上,將本文提出的KTSM方法和現(xiàn)有的GADDI、 SAPPER等方法進(jìn)行對(duì)比,在分別變化四種參數(shù)時(shí)的實(shí)驗(yàn)結(jié)果進(jìn)行比較和分析,驗(yàn)證了本文提出的子圖匹配方法在現(xiàn)實(shí)圖網(wǎng)絡(luò)和合成數(shù)據(jù)集上,都具有較好的查詢(xún)匹配能力,子圖匹配的效率得到了極大的提高。
【關(guān)鍵詞】：圖 近似子圖 容忍度 索引 子圖匹配
【學(xué)位授予單位】：遼寧大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2016
【分類(lèi)號(hào)】：O157.5
【目錄】：

• 摘要4-5
• abstract5-11
• 第1章 引言11-17
• 1.1 研究背景11-12
• 1.2 研究現(xiàn)狀12-14
• 1.3 研究?jī)?nèi)容14-15
• 1.4 本文組織結(jié)構(gòu)15-17
• 第2章 圖查詢(xún)問(wèn)題概述17-23
• 2.1 圖存儲(chǔ)17-18
• 2.2 圖查詢(xún)18-19
• 2.3 查詢(xún)匹配方法19-22
• 2.3.1 基于結(jié)構(gòu)的方法19-20
• 2.3.2 基于特征的方法20-21
• 2.3.3 基于節(jié)點(diǎn)的方法21-22
• 2.4 本章小結(jié)22-23
• 第3章 圖索引及查詢(xún)圖預(yù)處理23-37
• 3.1 圖索引23-26
• 3.1.1 標(biāo)簽圖23-24
• 3.1.2 索引24-26
• 3.2 子圖查詢(xún)26-30
• 3.2.1 精確子圖與近似子圖27-28
• 3.2.2 容忍度K28-29
• 3.2.3 單圖和多圖29-30
• 3.3 查詢(xún)圖預(yù)處理30-36
• 3.3.1 查詢(xún)圖ID31
• 3.3.2 近似子圖查詢(xún)邊序31-34
• 3.3.3 精確子圖查詢(xún)邊序34-36
• 3.4 本章小結(jié)36-37
• 第4章 查詢(xún)圖容忍度K的子圖匹配判定37-53
• 4.1 不等式屬性37-38
• 4.2 位串向量38-42
• 4.2.1 傳統(tǒng)Hash38-39
• 4.2.2 改進(jìn)Hash39-40
• 4.2.3 位串置位40-41
• 4.2.4 位串錯(cuò)誤率41-42
• 4.3 匹配判定42-43
• 4.4 子圖匹配43-52
• 4.4.1 近似子圖匹配43-47
• 4.4.2 精確子圖匹配47-52
• 4.5 本章小結(jié)52-53
• 第5章 實(shí)驗(yàn)及分析53-61
• 5.1 實(shí)驗(yàn)環(huán)境介紹53
• 5.2 實(shí)驗(yàn)數(shù)據(jù)集53-54
• 5.2.1 真實(shí)數(shù)據(jù)集54
• 5.2.2 合成數(shù)據(jù)集54
• 5.3 性能評(píng)估指標(biāo)54-55
• 5.4 實(shí)驗(yàn)結(jié)果分析55-60
• 5.4.1 真實(shí)數(shù)據(jù)集對(duì)比55-57
• 5.4.2 合成數(shù)據(jù)集對(duì)比57-60
• 5.5 本章小結(jié)60-61
• 第6章 總結(jié)與展望61-63
• 6.1 總結(jié)61
• 6.2 展望61-63
• 致謝63-65
• 參考文獻(xiàn)65-69
• 攻讀學(xué)位期間發(fā)表的學(xué)術(shù)論文及參加科研情況69

【參考文獻(xiàn)】

中國(guó)期刊全文數(shù)據(jù)庫(kù) 前2條

1 張碩;高宏;李建中;鄒兆年;;不確定圖數(shù)據(jù)庫(kù)中高效查詢(xún)處理[J];計(jì)算機(jī)學(xué)報(bào);2009年10期

2 周傲英;金澈清;王國(guó)仁;李建中;;不確定性數(shù)據(jù)管理技術(shù)研究綜述[J];計(jì)算機(jī)學(xué)報(bào);2009年01期

，

本文編號(hào)：813020