圖模型以點和邊描述實體和關系,相較于其他數(shù)據結構,更能簡潔有力的刻畫事務之間的復雜關系,因此被廣泛應用于眾多領域求解實際問題。隨著當今時代數(shù)據量的大規(guī)模增長,以大規(guī)模圖為模型的問題求解受到越來越多的關注,而子圖搜索問題作為圖論的重要子問題之一,具有深遠的研究意義和價值。目前的子圖搜索問題求解算法,大多僅適用于無權圖,且在大規(guī)模數(shù)據圖上的執(zhí)行效果并不十分理想。盡管近年來,部分研究提出并行求解大規(guī)模圖上的子圖搜索,但已有的算法對于一些常見限定性查詢執(zhí)行效率極低,甚至無法滿足查詢需求。本文針對子圖搜索問題中的一類限定性查詢進行創(chuàng)新和改進,主要研究內容如下:在已有的個性化子圖搜索問題上做擴展并進行形式化定義�，F(xiàn)有的子圖搜索問題中查詢圖節(jié)點均具有唯一屬性值,個性化子圖搜索問題同時要求部分區(qū)域的權值大于用戶設定的閾值。而在擴展的個性化子圖搜索問題中,查詢圖的節(jié)點分為兩類:一類節(jié)點的屬性值唯一;另一類節(jié)點的屬性值具有可選擇性。數(shù)據圖的節(jié)點屬性值均唯一。擴展的個性化子圖搜索即在數(shù)據圖中尋找子圖滿足:1)查詢圖中第一類節(jié)點的屬性值與子圖相應節(jié)點的屬性值相同;2)查詢圖中第二類節(jié)點的屬性值之一與子圖相應節(jié)... 

【文章來源】：中南民族大學湖北省

【文章頁數(shù)】：53 頁

【學位級別】：碩士

【文章目錄】：
摘要
ABSTRACT
第1章 緒論
    1.1 研究背景及意義
    1.2 國內外研究現(xiàn)狀
    1.3 本文主要工作
    1.4 本文組織結構
第2章 子圖搜索相關理論及技術
    2.1 圖相關定義
        2.1.1 圖模型
        2.1.2 子圖搜索
        2.1.3 個性化子圖搜索問題
    2.2 圖索引技術
    2.3 分布式技術
        2.3.1 MapReduce計算模型
        2.3.2 Hadoop框架
    2.4 本章小結
第3章 基于雙索引的多樣性子圖搜索算法
    3.1 多樣性子圖搜索問題
    3.2 索引的構建
        3.2.1 CP索引
        3.2.2 Vin索引
    3.3 多樣性子圖搜索算法
        3.3.1 DSSA算法
        3.3.2 優(yōu)化策略
        3.3.3 算法分析
    3.4 實驗
        3.4.1 實驗環(huán)境和數(shù)據集
        3.4.2 節(jié)點規(guī)模對效率的影響
        3.4.3 多值節(jié)點的節(jié)點值規(guī)模對效率的影響
    3.5 本章小結
第4章 多樣性子圖搜索算法的并行化實現(xiàn)
    4.1 問題分析
        4.1.1 數(shù)據圖劃分問題
        4.1.2 邊界子圖匹配問題
    4.2 數(shù)據圖處理
        4.2.1 基于定值域的數(shù)據圖劃分
        4.2.2 基于邊界邊的索引構建
        4.2.3 DLP算法
    4.3 PDSSA算法
        4.3.1 PDSSA描述
        4.3.2 PDSSA map階段
        4.3.3 PDSSA reduce階段
    4.4 實驗
        4.4.1 實驗環(huán)境和數(shù)據集
        4.4.2 DLP實驗結果及分析
        4.4.3 PDSSA實驗結果及分析
    4.5 本章小結
第5章 總結與展望
    5.1 本文總結
    5.2 未來工作展望
參考文獻
附錄A 攻讀學位期間獲得的成果及參加的項目
致謝


【參考文獻】：
期刊論文
[1]圖數(shù)據分析系統(tǒng)計算模型綜述[J]. 劉夢雅,劉燕兵,于靜,郭莉,孫志剛.  計算機應用研究. 2017(11)
[2]云計算中Hadoop技術研究與應用綜述[J]. 夏靖波,韋澤鯤,付凱,陳珍.  計算機科學. 2016(11)
[3]大規(guī)模數(shù)據圖上的個性化子圖匹配算法[J]. 楊艷,紀安娜,金虎.  計算機研究與發(fā)展. 2015(S1)
[4]大規(guī)模圖數(shù)據匹配技術綜述[J]. 于靜,劉燕兵,張宇,劉夢雅,譚建龍,郭莉.  計算機研究與發(fā)展. 2015(02)
[5]圖數(shù)據表示與壓縮技術綜述[J]. 張宇,劉燕兵,熊剛,賈焰,劉萍,郭莉.  軟件學報. 2014(09)
[6]圖索引技術研究綜述[J]. 劉雅輝,劉春陽,張鐵贏,程學旗.  山東大學學報(理學版). 2013(11)
[7]MapReduce并行編程模型研究綜述[J]. 李建江,崔健,王聃,嚴林,黃義雙.  電子學報. 2011(11)
[8]云計算環(huán)境下的大規(guī)模圖數(shù)據處理技術[J]. 于戈,谷峪,鮑玉斌,王志剛.  計算機學報. 2011(10)
[9]基于消息傳遞機制的MapReduce圖算法研究[J]. 潘巍,李戰(zhàn)懷,伍賽,陳群.  計算機學報. 2011(10)

博士論文
[1]圖數(shù)據查詢技術的研究[D]. 李先通.哈爾濱工業(yè)大學 2009

碩士論文
[1]基于Spark的子圖匹配算法研究與實現(xiàn)[D]. 郭騰.北京交通大學 2017
[2]高效子圖匹配算法研究[D]. 戴昕.北京交通大學 2016



本文編號：3044151