發(fā)布時間：2017-05-13 13:10

  本文關(guān)鍵詞：大規(guī)模DAG圖可達查詢與優(yōu)化方法研究，由筆耕文化傳播整理發(fā)布。

【摘要】：圖作為一種能描述復(fù)雜結(jié)構(gòu)化的通用數(shù)據(jù)結(jié)構(gòu),被廣泛應(yīng)用于XML數(shù)據(jù)庫、社會關(guān)系網(wǎng)絡(luò)、地理導(dǎo)航和本體查詢等新興領(lǐng)域。隨著信息技術(shù)中圖數(shù)據(jù)的極速增長,圖數(shù)據(jù)結(jié)構(gòu)變得日益復(fù)雜,圖數(shù)據(jù)的分析、存儲和管理均面臨前所未有的挑戰(zhàn)。作為大規(guī)模DAG圖數(shù)據(jù)分析中最常見的技術(shù),可達查詢扮演著一個最基礎(chǔ)的角色。然而大部分現(xiàn)有的可達查詢機制在面對大規(guī)模圖時呈現(xiàn)查詢效率低的問題。因此,針對大規(guī)模DAG圖能否高效地進行可達查詢和優(yōu)化對管理圖數(shù)據(jù)庫是至關(guān)重要的。針對上述問題,本文對大規(guī)模DAG圖的可達查詢和優(yōu)化方法進行了深入研究。首先提出了一種基于圖分層的標(biāo)簽索引方法(GSL,Graph Stratification Labeling),該方法將圖分層技術(shù)應(yīng)用到預(yù)處理過程中,利用二分圖的最大匹配圖性質(zhì)將分層后各節(jié)點集鏈接成一條條不相交的鏈?zhǔn)浇Y(jié)構(gòu),進而將大規(guī)模圖壓縮至最小化,最后根據(jù)各節(jié)點的性質(zhì)和節(jié)點間的可達關(guān)系,為圖中節(jié)點分別創(chuàng)建其獨有的鏈內(nèi)標(biāo)簽和鏈間標(biāo)簽。其次,基于GSL索引方法提出了兩種新的可達查詢方法:鏈內(nèi)可達查詢方法和鏈間可達查詢方法。同時基于圖分層和最大匹配圖算法的性質(zhì),提出了兩種可達查詢優(yōu)化方法:基于圖分層性質(zhì)的優(yōu)化方法和基于傳遞性的優(yōu)化方法。最后,通過在模擬數(shù)據(jù)集和真實數(shù)據(jù)集上將本文的可達查詢算法,及其索引算法和現(xiàn)有的算法進行實驗比較和分析,驗證了本文提出的可達查詢方法在現(xiàn)實圖網(wǎng)絡(luò)、大規(guī)模稀疏圖和稠密圖上都具有很好的查詢性能,大大的提高可達查詢的效率。
【關(guān)鍵詞】：大規(guī)模DAG圖 可達性查詢 圖分層 最大匹配圖 標(biāo)簽索引方法
【學(xué)位授予單位】：遼寧大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：O157.5;TP311.13
【目錄】：

• 摘要4-5
• ABSTRACT5-10
• 第1章 引言10-16
• 1.1 研究背景10-12
• 1.2 國內(nèi)外研究現(xiàn)狀12-13
• 1.3 研究內(nèi)容13-14
• 1.4 本文組織結(jié)構(gòu)14-16
• 第2章 可達查詢相關(guān)方法16-24
• 2.1 傳統(tǒng)方法16
• 2.2 中小規(guī)模圖的可達查詢16-21
• 2.2.1 鏈分解方法16-18
• 2.2.2 樹覆蓋方法18-19
• 2.2.3 路徑樹方法19-20
• 2.2.4 Hop編碼方法20-21
• 2.3 大規(guī)模圖的可達查詢21-23
• 2.4 本章小結(jié)23-24
• 第3章 基于圖分層的標(biāo)簽索引方法24-36
• 3.1 索引方法概述24-25
• 3.2 圖分層25-28
• 3.2.1 基本符號定義25-26
• 3.2.2 圖分層算法26-28
• 3.3 創(chuàng)建最大匹配圖28-33
• 3.3.1 相關(guān)概念28-30
• 3.3.2 創(chuàng)建最大匹配圖算法30-33
• 3.4 生成可達標(biāo)簽33-35
• 3.5 本章小結(jié)35-36
• 第4章 基于GSL的可達查詢方法36-46
• 4.1 問題定義36
• 4.2 鏈內(nèi)可達查詢36-39
• 4.3 鏈間可達查詢39-41
• 4.4 可達查詢優(yōu)化41-45
• 4.4.1 基于圖分層性質(zhì)的優(yōu)化41-43
• 4.4.2 基于傳遞性的優(yōu)化43-45
• 4.5 本章小結(jié)45-46
• 第5章 實驗及分析46-54
• 5.1 實驗環(huán)境介紹46
• 5.2 實驗數(shù)據(jù)集46-47
• 5.2.1 模擬數(shù)據(jù)集47
• 5.2.2 真實數(shù)據(jù)集47
• 5.3 性能評估指標(biāo)47-48
• 5.4 實驗結(jié)果分析48-53
• 5.4.1 模擬數(shù)據(jù)集實驗48-51
• 5.4.2 真實數(shù)據(jù)集實驗51-53
• 5.5 本章小結(jié)53-54
• 第6章 總結(jié)與展望54-56
• 6.1 總結(jié)54-55
• 6.2 展望55-56
• 致謝56-57
• 參考文獻57-60
• 攻讀學(xué)位期間發(fā)表的學(xué)術(shù)論文及參加科研情況60-61

【參考文獻】

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

1 舒虎;崇志宏;倪巍偉;盧山;徐立臻;;X-Hop:傳遞閉包的多跳數(shù)壓縮存儲和快速可達性查詢[J];計算機科學(xué);2012年03期

2 袁野;王國仁;;基于閾值的概率圖可達查詢[J];計算機學(xué)報;2010年12期

3 范時平;潘淑琴;羅啟涵;;一種新的基于遞歸分解的圖可達性查詢算法[J];計算機應(yīng)用研究;2014年12期

4 富麗貞;孟小峰;;大規(guī)模圖數(shù)據(jù)可達性索引技術(shù):現(xiàn)狀與展望[J];計算機研究與發(fā)展;2015年01期

5 李鳴鵬;高宏;鄒兆年;;基于圖壓縮的k可達查詢處理[J];軟件學(xué)報;2014年04期

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

1 史嶺峰;基于社交網(wǎng)絡(luò)好友關(guān)系的圖查詢算法研究與應(yīng)用[D];南京理工大學(xué);2012年

  本文關(guān)鍵詞：大規(guī)模DAG圖可達查詢與優(yōu)化方法研究，，由筆耕文化傳播整理發(fā)布。

本文編號：362628