本文關鍵詞：基于容忍度K的子圖查詢匹配方法研究

  更多相關文章： 圖 近似子圖 容忍度 索引 子圖匹配

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

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

【參考文獻】

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

1 張碩;高宏;李建中;鄒兆年;;不確定圖數(shù)據(jù)庫中高效查詢處理[J];計算機學報;2009年10期

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

，

本文編號：813020