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

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

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

• 摘要4-5
• ABSTRACT5-10
• 第1章 引言10-16
• 1.1 研究背景10-12
• 1.2 國(guó)內(nèi)外研究現(xiàn)狀12-13
• 1.3 研究?jī)?nèi)容13-14
• 1.4 本文組織結(jié)構(gòu)14-16
• 第2章 可達(dá)查詢相關(guān)方法16-24
• 2.1 傳統(tǒng)方法16
• 2.2 中小規(guī)模圖的可達(dá)查詢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ī)模圖的可達(dá)查詢21-23
• 2.4 本章小結(jié)23-24
• 第3章 基于圖分層的標(biāo)簽索引方法24-36
• 3.1 索引方法概述24-25
• 3.2 圖分層25-28
• 3.2.1 基本符號(hào)定義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 生成可達(dá)標(biāo)簽33-35
• 3.5 本章小結(jié)35-36
• 第4章 基于GSL的可達(dá)查詢方法36-46
• 4.1 問(wèn)題定義36
• 4.2 鏈內(nèi)可達(dá)查詢36-39
• 4.3 鏈間可達(dá)查詢39-41
• 4.4 可達(dá)查詢優(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章 實(shí)驗(yàn)及分析46-54
• 5.1 實(shí)驗(yàn)環(huán)境介紹46
• 5.2 實(shí)驗(yàn)數(shù)據(jù)集46-47
• 5.2.1 模擬數(shù)據(jù)集47
• 5.2.2 真實(shí)數(shù)據(jù)集47
• 5.3 性能評(píng)估指標(biāo)47-48
• 5.4 實(shí)驗(yàn)結(jié)果分析48-53
• 5.4.1 模擬數(shù)據(jù)集實(shí)驗(yàn)48-51
• 5.4.2 真實(shí)數(shù)據(jù)集實(shí)驗(yàn)51-53
• 5.5 本章小結(jié)53-54
• 第6章 總結(jié)與展望54-56
• 6.1 總結(jié)54-55
• 6.2 展望55-56
• 致謝56-57
• 參考文獻(xiàn)57-60
• 攻讀學(xué)位期間發(fā)表的學(xué)術(shù)論文及參加科研情況60-61

【參考文獻(xiàn)】

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

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

2 袁野;王國(guó)仁;;基于閾值的概率圖可達(dá)查詢[J];計(jì)算機(jī)學(xué)報(bào);2010年12期

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

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

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

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

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

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

本文編號(hào)：362628