發(fā)布時(shí)間：2023-04-30 06:25

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

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

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

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



本文編號(hào)：3806611