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

【文章來源】：燕山大學(xué)河北省

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

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

【文章目錄】：
摘要
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 可達(dá)性查詢的基本知識
    2.3 可達(dá)性查詢的相關(guān)算法
        2.3.1 Label-Only類可達(dá)性算法
        2.3.2 Label+G類可達(dá)性算法
    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章 高效可達(dá)性查詢算法IERch+

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



本文編號：2949692

suoshi