發(fā)布時間：2022-02-21 06:01

　　圖常用的查詢算法有可達性、最短路徑距離和最寬路徑查詢等,傳統(tǒng)查詢算法有兩種:一種是求解完整傳遞閉包,即預計算出所有的結(jié)果,那么查詢效率為（1）;另一種則是使用修改的Dijkstra算法或其他算法直接在原圖上進行搜索,空間開銷為（1）。而近年來圖規(guī)�？焖僭鲩L,其節(jié)點和邊的總數(shù)可以達到億級規(guī)模。針對如此大規(guī)模的圖,前者查詢效率雖高,但是空間開銷使其難以擴展;后者雖然空間開銷（1）很低,但直接在原圖搜索的算法往往因其過高的時間復雜度,無法滿足一些實時性要求很高的應用。因此在大規(guī)模圖中,如何進行快速高效地查詢是極具挑戰(zhàn)意義的。面向億級圖的高效索引和查詢系統(tǒng)是為了解決傳統(tǒng)算法在大規(guī)模圖處理中,查詢效率低或者空間復雜度過高的問題。該系統(tǒng)基于2-hop label索引結(jié)構(gòu),采用空間換時間的思想,在查詢效率和空間復雜度之間獲得平衡。并提出了一個基于剪枝思想的最寬路徑索引算法,該算法在處理大規(guī)模圖時,能使索引規(guī)模顯著降低。算法為每個節(jié)點依次執(zhí)行剪枝的Dijkstra算法,并產(chǎn)生索引標簽。其能減少索引時間和索引大小的核心關鍵是引入一個剪枝的操作。除此之外,本系統(tǒng)還集成了能支持億級規(guī)模圖的最短路徑、可達性查... 

【文章來源】：華中科技大學湖北省211工程院校985工程院校教育部直屬院校

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

【學位級別】：碩士

【文章目錄】：
摘要
Abstract
1 緒論
    1.1 項目研究背景及意義
    1.2 國內(nèi)外研究現(xiàn)狀
    1.3 本文主要工作
    1.4 論文組織結(jié)構(gòu)
2 最寬路徑的索引算法設計
    2.1 相關定義
    2.2 問題與挑戰(zhàn)
    2.3 算法設計
    2.4 節(jié)點排序策略
    2.5 算法正確性證明
    2.6 查詢效率分析
    2.7 本章小結(jié)
3 系統(tǒng)設計與實現(xiàn)
    3.1 系統(tǒng)架構(gòu)
    3.2 索引構(gòu)建
    3.3 查詢引擎
    3.4 本章小結(jié)
4 系統(tǒng)測試與性能分析
    4.1 系統(tǒng)實現(xiàn)與實驗環(huán)境
    4.2 測試數(shù)據(jù)集
    4.3 測試方法
    4.4 最寬路徑算法性能測試
    4.5 集成模塊測試
    4.6 本章小結(jié)
5 總結(jié)及展望
致謝
參考文獻
附錄1 攻讀碩士學位期間申請的計算機軟件著作權(quán)
附錄2 攻讀碩士學位期間參與的項目


【參考文獻】：
期刊論文
[1]一種基于懸掛頂點關聯(lián)索引的最短路徑查詢算法[J]. 陳偉,樓志斌,楊清章.  燕山大學學報. 2018(03)
[2]基于頂點關聯(lián)索引的最短路徑查詢算法研究[J]. 余靖,楊清章.  高技術通訊. 2017(Z2)
[3]基于雙區(qū)間標簽的大規(guī)模圖可達性索引[J]. 李婷婷,古天龍.  桂林電子科技大學學報. 2017(04)
[4]基于QoS的服務個性化選擇路由[J]. 劉巖,劉建明,任莉莉.  計算機工程與設計. 2016(04)
[5]尋找最大帶寬的獨立路徑對算法[J]. 謝政,張曉明,陳摯.  國防科技大學學報. 2012(05)
[6]關于實際構(gòu)造最大帶寬路徑算法的研究[J]. 陳建二,王偉平,張祖平.  福州大學學報(自然科學版). 2001(04)



本文編號：3636645