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

【文章來(lái)源】：華中科技大學(xué)湖北省211工程院校985工程院校教育部直屬院校

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

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

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


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



本文編號(hào)：3636645