近年來,超大規(guī)模復雜圖和社交圖的處理成為業(yè)界關注的熱點問題。與傳統(tǒng)數(shù)據(jù)處理相比,除規(guī)模超大外,數(shù)據(jù)往往表現(xiàn)為邏輯上的圖結(jié)構(gòu),數(shù)據(jù)的處理表現(xiàn)為點和邊不斷迭代。傳統(tǒng)關系型數(shù)據(jù)庫在存儲和處理兩方面對大規(guī)模圖數(shù)據(jù)的支持有限,本文主要討論在構(gòu)建分布式圖數(shù)據(jù)庫中存儲方面的關鍵問題。在分布式圖存儲系統(tǒng)中,圖的存儲策略和劃分算法對整個系統(tǒng)起著很重要的作用。優(yōu)秀的劃分算法能最大限度保留圖自身結(jié)構(gòu),減少切割邊規(guī)模,保證子分區(qū)內(nèi)部的鄰近性,這能從根本上減少處理數(shù)據(jù)時帶來的網(wǎng)絡開銷。存儲策略則負責為劃分后的圖構(gòu)建存儲模型,高效組織數(shù)據(jù)索引,為查詢和寫入提供支撐。本文著重關注三個方面,一是提高劃分算法并行執(zhí)行效率并保證一定劃分效果;二是設計針對圖數(shù)據(jù)特點的數(shù)據(jù)模型;三是針對圖數(shù)據(jù)設計和實現(xiàn)一套可靠的分布式存儲解決方案。本文所做的工作主要如下:1)首先介紹圖數(shù)據(jù)庫的產(chǎn)生和發(fā)展,然后分析當前圖數(shù)據(jù)庫對底層圖存儲系統(tǒng)的需求,并介紹圖劃分算法的分類和研究現(xiàn)狀。最后深入研究實現(xiàn)分布式圖存儲系統(tǒng)所需要的相關技術(shù)。2)本文研究了當前圖數(shù)據(jù)領域主流劃分算法,分析各自的優(yōu)缺點。對HDRF劃分算法在并行執(zhí)行場景下的劃分效率進行優(yōu)化... 

【文章來源】：電子科技大學四川省 211工程院校 985工程院校 教育部直屬院校

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

【學位級別】：碩士

【部分圖文】：

算法執(zhí)行時間開銷對比圖

電子科技大學碩士學位論文60第五章測試本章測試的對象主要分為兩個部分：劃分算法和圖存儲系統(tǒng)。每個部分分別以功能測試和性能測試兩個方面來展示。其中功能測試包括劃分算法的導入和劃分后分區(qū)的負載均衡以及圖存儲系統(tǒng)的數(shù)據(jù)寫入和查詢功能。性能測試包括劃分算法的執(zhí)行時間和劃分效果以及圖存儲系統(tǒng)的吞吐能力。5.1P-HDRF劃分算法測試5.1.1測試環(huán)境表5-1劃分算法測試配置表CPUIntel(R)Xeon(R)CPUE5-2603@1.80GHz內(nèi)存62GB網(wǎng)卡1000Mb/s硬盤256G操作系統(tǒng)Linuxubuntu4.4.0-161-generic(x86_64)開發(fā)工具Vim5.1.2圖劃分算法功能測試P-HDRF功能測試主要是為了測試其是否能保證分區(qū)的負載均衡。負載均衡的測試數(shù)據(jù)是社交平臺的開源數(shù)據(jù)。劃分算法從本地磁盤讀入數(shù)據(jù)，并將其劃分為為4個子分區(qū)。我們分別以兩個數(shù)量級的數(shù)據(jù)做了測試，測試結(jié)果如圖5-1和圖5-2所示。圖5-1數(shù)據(jù)集一測試結(jié)果圖

第五章測試61由圖5-1可知，該測試文件約有八十二萬八千條邊、七萬七千個頂點。劃分之后，所有子分區(qū)的最大負載和最小負載如圖5-1中紅線框所示,分區(qū)的負載能夠達到很好的均衡狀態(tài)。圖5-2數(shù)據(jù)集二測試結(jié)果圖圖5-2所示的測試文件總共有一千萬條邊、五百一十五萬個頂點。劃分之后每個分區(qū)的負載依然能夠保證負載均衡。圖5-2第一處紅線框的數(shù)據(jù)依次為劃分后總頂點數(shù)和劃分前的總頂點數(shù)。第二處紅線框的數(shù)據(jù)表明分區(qū)負載的最大頂點和邊數(shù)量以及負載最少的頂點和邊數(shù)量。結(jié)合這三個指標可以得出，改進后的算法能夠滿足劃分后分區(qū)負載均衡的目標，并且通過這幾個指標和重復度因子也可以看出算法的劃分效果也符合預期。5.1.3圖劃分算法性能測試5.1.3.1窗口值的測試本文提出的P-HDRF版本是針對HDRF劃分算法在并行處理場景中的優(yōu)化。在優(yōu)化算法中我們引入了窗口，在實際測試中，窗口值的變化會引起算法執(zhí)行效率的變化。圖5-3測試在不同線程數(shù)下調(diào)節(jié)窗口值的大小，然后測試劃分算法執(zhí)行的時間開銷。由圖可知，在將線程數(shù)設置為1的情況下，增大窗口值后算法的執(zhí)行時間會明顯減少，尤其在增大窗口值的初期，執(zhí)行時間減少得最明顯。當把窗口值設定為比16更大時，執(zhí)行時間并沒有明顯的變化。測試實驗增加了對比數(shù)據(jù)，引入了不同線程數(shù)，來佐證之前的實驗結(jié)果�？梢钥吹�，對于不同的線程數(shù)目，當調(diào)節(jié)窗口

【參考文獻】：
期刊論文
[1]NoSQL數(shù)據(jù)庫綜述[J]. 吾木提·那合曼.  電子世界. 2015(17)
[2]大規(guī)模圖數(shù)據(jù)劃分算法綜述[J]. 許金鳳,董一鴻,王詩懿,何賢芒,陳華輝.  電信科學. 2014(07)
[3]數(shù)據(jù)庫技術(shù)發(fā)展綜述[J]. 向海華.  現(xiàn)代情報. 2003(12)

碩士論文
[1]基于分布式圖計算的大規(guī)模網(wǎng)絡分析系統(tǒng)的研究[D]. 趙炳.北京郵電大學 2018
[2]圖分布式計算的通信優(yōu)化研究[D]. 常東陽.遼寧大學 2017



本文編號：3571222