有向無環(huán)圖(DAG)的可達性查詢處理是圖數(shù)據(jù)管理中的熱點問題之一,可以應用到現(xiàn)實生活中的很多領(lǐng)域,包括語義網(wǎng)、互聯(lián)網(wǎng)、電信網(wǎng)、無線傳感網(wǎng)絡、社交網(wǎng)絡及生物信息網(wǎng)等�？蛇_性查詢就是在有向無環(huán)圖G上,給定任意的2個結(jié)點u和v,回答u是否能夠到達v。通過分析現(xiàn)有可達性查詢算法,發(fā)現(xiàn)已有的算法構(gòu)建索引的時間較長,查詢效率低。本文主要從以上2個方面對可達性查詢處理進行研究,研究內(nèi)容如下。首先,提出基于影子定位的索引構(gòu)建算法SP。SP算法基于區(qū)間擴展策略為每個結(jié)點設定標簽。給定需要處理的n個結(jié)點,不同于以往算法需要多次的遍歷才能完成當前結(jié)點的處理,SP算法基于影子定位技術(shù),將待處理結(jié)點分別存放在待處理棧和待掃描鏈表中,待處理棧中每個結(jié)點記錄了其在待掃描鏈表中的位置,從而將已有方法的O(logn)搜索代價降低為O(1)代價,加速了索引構(gòu)建的效率。其次,提出雙向編碼方案和基于巨大結(jié)點的剪枝策略來提升查詢處理的效率。通過正向和反向進行編碼,為每個結(jié)點指定相應的索引標簽,增強了區(qū)間過濾的能力。為了進一步的增強可達查詢的處理能力,提出巨大結(jié)點的位標簽過濾策略。該策略選取k個度最大的hop結(jié)點,根據(jù)每個結(jié)點與... 

【文章來源】：燕山大學河北省

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

【學位級別】：碩士

【文章目錄】：
摘要
Abstract
第1章 緒論
    1.1 研究背景
    1.2 研究現(xiàn)狀
    1.3 本文研究內(nèi)容
    1.4 本文組織結(jié)構(gòu)
第2章 基礎(chǔ)知識概述
    2.1 相關(guān)數(shù)據(jù)結(jié)構(gòu)及其定義
    2.2 可達性查詢的基本知識
    2.3 可達性查詢的相關(guān)算法
        2.3.1 Label-Only類可達性算法
        2.3.2 Label+G類可達性算法
    2.4 本章小結(jié)
第3章 基于影子定位索引構(gòu)建算法SP
    3.1 問題分析
    3.2 SP基本思想
    3.3 算法描述
        3.3.1 索引構(gòu)建
        3.3.2 查詢處理
    3.4 本章小結(jié)
+">第4章 高效可達性查詢算法IERch+

    4.1 問題分析
    4.2 高效可達性查詢索引的生成
        4.2.1 雙向編碼方案
        4.2.2 基于巨大結(jié)點的剪枝策略
        4.2.3 查詢處理
    4.3 本章小結(jié)
第5章 實驗分析
    5.1 實驗簡介
    5.2 數(shù)據(jù)集
    5.3 評價指標
+可達性查詢算法性能分析">    5.4 IERch⁺可達性查詢算法性能分析
        5.4.1 Label+G類算法性能比較分析
        5.4.2 區(qū)間擴展類算法性能比較分析
    5.5 本章小結(jié)
結(jié)論
參考文獻
攻讀碩士學位期間承擔的科研任務與主要成果
致謝



本文編號：2949692

suoshi