歷史圖作為刻畫圖網(wǎng)絡(luò)隨著時間維度不斷的變化的圖數(shù)據(jù)結(jié)構(gòu),正在越來越多的場景展現(xiàn)其應(yīng)用和研究價值。本文從歷史圖數(shù)據(jù)入手,著手于研究歷史圖數(shù)據(jù)的存儲和計算方法。基于Rocks DB存儲引擎,本文設(shè)計并實現(xiàn)了歷史圖數(shù)據(jù)庫Hist DB對歷史圖數(shù)據(jù)進(jìn)行高效的存儲和檢索。Hist DB基于K-V存儲模式存儲歷史圖的圖增量數(shù)據(jù),并結(jié)合歷史圖的頂點檢索、圖增量檢索、歷史鄰居檢索和快照檢索四類檢索設(shè)計并實現(xiàn)了高效的數(shù)據(jù)檢索接口。此外,Hist DB基于分塊的底層存儲,設(shè)計了數(shù)據(jù)索引區(qū)塊對檢索進(jìn)行優(yōu)化,實驗表明,Hist DB的索引優(yōu)化機(jī)制可以有效地提升一些數(shù)據(jù)檢索接口的性能。本文結(jié)合歷史圖上查詢需求,基于Gremlin靜態(tài)圖查詢語言并引入時間維度設(shè)計了歷史圖查詢語言Hist QL。基于Hist QL語言,本文還設(shè)計實現(xiàn)了歷史圖查詢計算框架Hist Query以對查詢語句進(jìn)行計算,Hist Query使用嵌套的計算單元管理方式,可以實現(xiàn)多層次、多粒度的資源管理和計算調(diào)度。此外,本文還基于所設(shè)計了無鎖通信機(jī)制,實現(xiàn)了Hist Query的多線程計算框架。本文還基于實驗測試,展示了Hist Query的多線...

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

【學(xué)位級別】：碩士

【文章目錄】：
摘要
ABSTRACT
第1章 緒論
    1.1 課題背景及研究的目的和意義
    1.2 歷史圖數(shù)據(jù)的相關(guān)研究概況
        1.2.1 歷史圖數(shù)據(jù)存儲管理技術(shù)的研究概況
        1.2.2 歷史圖數(shù)據(jù)計算與分析技術(shù)的研究概況
    1.3 本文的主要研究內(nèi)容
        1.3.1 歷史圖數(shù)據(jù)的存儲與檢索技術(shù)
        1.3.2 歷史圖的結(jié)構(gòu)化查詢技術(shù)
        1.3.3 歷史圖路徑分析技術(shù)
第2章 歷史圖數(shù)據(jù)的存儲與檢索技術(shù)
    2.1 引言
    2.2 存儲原理設(shè)計
        2.2.1 歷史圖存儲的內(nèi)在需求和存儲引擎選擇
        2.2.2 底層存儲分布與數(shù)據(jù)寫入機(jī)制
    2.3 數(shù)據(jù)檢索接口設(shè)計與檢索機(jī)制
        2.3.1 前綴匹配與迭代器遍歷機(jī)制
        2.3.2 數(shù)據(jù)檢索接口設(shè)計
        2.3.3 基于索引的檢索優(yōu)化機(jī)制
    2.4 實驗測試與評估
        2.4.1 寫性能測試
        2.4.2 基本迭代器檢索性能測試
        2.4.3 跳躍迭代器檢索性能與索引優(yōu)化測試
    2.5 本章小結(jié)
第3章 歷史圖的結(jié)構(gòu)化查詢技術(shù)
    3.1 引言
    3.2 歷史圖的結(jié)構(gòu)化查詢語言設(shè)計
        3.2.1 結(jié)構(gòu)化查詢語言的表示形式
        3.2.2 查詢算子設(shè)計
        3.2.3 查詢語句示例
    3.3 查詢計算框架
        3.3.1 查詢計算框架的內(nèi)部結(jié)構(gòu)和組織形式
        3.3.2 計算數(shù)據(jù)的信息載體與尋址機(jī)制
        3.3.3 資源調(diào)度與計算流程
        3.3.4 查詢計算的終止機(jī)制
    3.4 復(fù)雜查詢算子實現(xiàn)
        3.4.1 條件循環(huán)算子
        3.4.2 嵌套分支過濾算子
    3.5 查詢計算的多線程實現(xiàn)
        3.5.1 多線程下的計算資源劃分
        3.5.2 多線程下的查詢計算框架結(jié)構(gòu)
        3.5.3 多線程無鎖通信機(jī)制
        3.5.4 多線程環(huán)境下的計算終止機(jī)制
    3.6 實驗測試與性能評價
        3.6.1 數(shù)據(jù)集
        3.6.2 多線程查詢性能測試
        3.6.3 配置參數(shù)的單變量測試
        3.6.4 提前終止機(jī)制對性能影響的測試
        3.6.5 實驗總結(jié)
    3.7 本章小結(jié)
第4章 歷史圖的路徑搜索技術(shù)
    4.1 引言
    4.2 歷史圖的擴(kuò)展定義
    4.3 歷史圖路徑的定義
    4.4 歷史圖路徑的效用值定義
    4.5 歷史圖路徑搜索問題
    4.6 歷史圖路徑搜索基本算法
        4.6.1 算法設(shè)計與實現(xiàn)
        4.6.2 算法復(fù)雜性分析
    4.7 歷史圖路徑搜索的一趟掃描優(yōu)化算法
        4.7.1 算法設(shè)計與實現(xiàn)
        4.7.2 算法復(fù)雜性分析
    4.8 實驗測試與評價
        4.8.1 實驗設(shè)置與數(shù)據(jù)集
        4.8.2 算法效率測試
        4.8.3 算法的數(shù)據(jù)敏感性測試
    4.9 本章小結(jié)
結(jié)論
參考文獻(xiàn)
攻讀碩士學(xué)位期間發(fā)表的論文及其它成果
致謝



本文編號：3806611