發(fā)布時(shí)間：2017-08-01 06:02

  本文關(guān)鍵詞：大規(guī)模圖中最短路徑查詢(xún)方法研究

  更多相關(guān)文章： 大規(guī)模圖 最短路徑查詢(xún) 樹(shù)分解 距離標(biāo)簽 關(guān)鍵點(diǎn)集合

【摘要】：圖作為描述現(xiàn)實(shí)世界中實(shí)體及實(shí)體間關(guān)系的基本數(shù)據(jù)結(jié)構(gòu),被廣泛應(yīng)用于復(fù)雜網(wǎng)絡(luò)分析、生物信息學(xué)、地理導(dǎo)航、物流規(guī)劃等新興領(lǐng)域。隨著大數(shù)據(jù)時(shí)代的到來(lái),圖數(shù)據(jù)規(guī)模迅速增長(zhǎng),同時(shí)數(shù)據(jù)的拓?fù)浣Y(jié)構(gòu)也變得越來(lái)越復(fù)雜,導(dǎo)致大規(guī)模圖數(shù)據(jù)的分析處理面臨著巨大的挑戰(zhàn)。最短路徑查詢(xún)是圖論研究中的核心內(nèi)容之一,現(xiàn)實(shí)世界中的很多問(wèn)題都可以轉(zhuǎn)化為最短路徑問(wèn)題求解。然而隨著網(wǎng)絡(luò)規(guī)模的增大,經(jīng)典的最短路徑查詢(xún)方法已無(wú)法滿(mǎn)足大規(guī)模圖的查詢(xún)需求,設(shè)計(jì)更為有效的方法實(shí)現(xiàn)大規(guī)模圖上的最短路徑查詢(xún)以滿(mǎn)足各種應(yīng)用需求具有一定的研究意義。本文對(duì)大規(guī)模圖中最短路徑查詢(xún)方法進(jìn)行了深入研究,發(fā)現(xiàn)無(wú)論是近似最短路徑查詢(xún)還是精確最短路徑查詢(xún),在涉及大規(guī)模數(shù)據(jù)場(chǎng)景的現(xiàn)實(shí)應(yīng)用中,預(yù)處理技術(shù)通常都被用來(lái)作為提高查詢(xún)效率的重要手段,預(yù)處理工作完成之后,查詢(xún)算法通常能夠以常數(shù)時(shí)間響應(yīng)查詢(xún)結(jié)果。因此,基于預(yù)處理的思想,本文首先提出了一種大規(guī)模圖中近似最短路徑查詢(xún)方法,即關(guān)鍵點(diǎn)引導(dǎo)的近似最短路徑查詢(xún)方法,該方法選擇K個(gè)頂點(diǎn)作為圖中的關(guān)鍵點(diǎn),預(yù)處理中只計(jì)算并存儲(chǔ)與關(guān)鍵點(diǎn)相關(guān)的最短路徑,可有效減少冗余數(shù)據(jù)量的存儲(chǔ),同時(shí)提高預(yù)處理效率。在查詢(xún)過(guò)程中,根據(jù)關(guān)鍵點(diǎn)估計(jì)最短路徑,將源點(diǎn)與目的點(diǎn)之間的最短路徑轉(zhuǎn)化為源點(diǎn)與關(guān)鍵點(diǎn)之間,關(guān)鍵點(diǎn)之間,以及關(guān)鍵點(diǎn)與目的點(diǎn)之間的最短路徑之和,從而縮小了搜索區(qū)域的范圍,有效提高最短路徑的查詢(xún)效率。然而關(guān)鍵點(diǎn)作為圖中的“樞紐”頂點(diǎn),最短路徑查詢(xún)通過(guò)關(guān)鍵點(diǎn)采用上確界方式估計(jì)最短路徑,本文方法會(huì)存在一定的誤差,但通過(guò)實(shí)驗(yàn)驗(yàn)證可以在可接受的誤差范圍內(nèi)完成大規(guī)模圖中的近似最短路徑查詢(xún)。為滿(mǎn)足精確查詢(xún)的需求并提高預(yù)處理效率,本文提出了基于樹(shù)分解與標(biāo)簽覆蓋(Tree Decomposition and Label Cover)的最短路徑查詢(xún)方法,該方法首先通過(guò)樹(shù)分解將大規(guī)模圖映射成樹(shù)結(jié)構(gòu)；其次在樹(shù)分解基礎(chǔ)上創(chuàng)建最小化的標(biāo)簽集合覆蓋樹(shù)結(jié)構(gòu),并優(yōu)化樹(shù)結(jié)構(gòu)和距離標(biāo)簽結(jié)構(gòu),有效減少冗余數(shù)據(jù)存儲(chǔ)并縮小遍歷頂點(diǎn)范圍,提高了預(yù)處理效率的同時(shí)降低了預(yù)處理開(kāi)銷(xiāo)；最后在查詢(xún)時(shí),利用預(yù)處理創(chuàng)建的索引結(jié)構(gòu),只需遍歷一次樹(shù)結(jié)構(gòu)即可完成查詢(xún),進(jìn)一步提高了查詢(xún)效率。最后,本文通過(guò)和已有的最短路徑查詢(xún)方法進(jìn)行實(shí)驗(yàn)對(duì)比分析,驗(yàn)證了本文提出的兩種最短路徑查詢(xún)方法均具有良好的預(yù)處理效率和查詢(xún)效率。
【關(guān)鍵詞】：大規(guī)模圖 最短路徑查詢(xún) 樹(shù)分解 距離標(biāo)簽 關(guān)鍵點(diǎn)集合
【學(xué)位授予單位】：遼寧大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2016
【分類(lèi)號(hào)】：TP301.6;O157.5
【目錄】：

• 摘要4-6
• ABSTRACT6-13
• 第1章 緒論13-18
• 1.1 研究背景13-14
• 1.2 國(guó)內(nèi)外研究現(xiàn)狀14-15
• 1.3 研究?jī)?nèi)容15-16
• 1.4 本文組織結(jié)構(gòu)16-18
• 第2章 最短路徑查詢(xún)方法綜述18-24
• 2.1 模型與問(wèn)題描述18-19
• 2.1.1 圖的定義與模型18
• 2.1.2 問(wèn)題描述18-19
• 2.2 方法綜述19-23
• 2.2.1 基于限制區(qū)域搜索技術(shù)的最短路徑查詢(xún)方法19-20
• 2.2.2 基于目標(biāo)引導(dǎo)技術(shù)的最短路徑查詢(xún)方法20-22
• 2.2.3 基于分層技術(shù)的最短路徑查詢(xún)方法22-23
• 2.3 本章小結(jié)23-24
• 第3章 關(guān)鍵點(diǎn)引導(dǎo)的近似最短路徑查詢(xún)24-37
• 3.1 相關(guān)定義及方法概述24-26
• 3.1.1 基本符號(hào)定義24-25
• 3.1.2 方法概述25-26
• 3.2 關(guān)鍵點(diǎn)集合選取26-32
• 3.2.1 接近中心點(diǎn)選擇27-29
• 3.2.2 關(guān)鍵點(diǎn)篩選29-32
• 3.3 創(chuàng)建距離標(biāo)簽庫(kù)32-33
• 3.4 最短路徑查詢(xún)33-35
• 3.5 本章小結(jié)35-37
• 第4章 樹(shù)分解與標(biāo)簽覆蓋的最短路徑查詢(xún)方法37-51
• 4.1 相關(guān)定義及方法概述37-39
• 4.1.1 基本符號(hào)定義37-38
• 4.1.2 方法概述38-39
• 4.2 TDLC方法39-46
• 4.2.1 樹(shù)分解39-40
• 4.2.2 創(chuàng)建標(biāo)簽覆蓋40-46
• 4.3 最短路徑查詢(xún)46-50
• 4.4 本章小結(jié)50-51
• 第5章 實(shí)驗(yàn)及分析51-60
• 5.1 實(shí)驗(yàn)環(huán)境51
• 5.2 實(shí)驗(yàn)數(shù)據(jù)集51-52
• 5.3 關(guān)鍵引導(dǎo)的近似最短路徑查詢(xún)的實(shí)驗(yàn)結(jié)果與分析52-55
• 5.3.1 性能評(píng)估指標(biāo)52-53
• 5.3.2 實(shí)驗(yàn)結(jié)果與分析53-55
• 5.4 樹(shù)分解與標(biāo)簽覆蓋的最短路徑查詢(xún)方法的實(shí)驗(yàn)結(jié)果與分析55-59
• 5.4.1 性能評(píng)估指標(biāo)55-56
• 5.4.2 實(shí)驗(yàn)結(jié)果與分析56-59
• 5.5 本章小結(jié)59-60
• 第6章 總結(jié)與展望60-62
• 6.1 總結(jié)60-61
• 6.2 展望61-62
• 致謝62-63
• 參考文獻(xiàn)63-66
• 攻讀學(xué)位期間發(fā)表的學(xué)術(shù)論文及參加科研情況66

【參考文獻(xiàn)】

中國(guó)期刊全文數(shù)據(jù)庫(kù) 前2條

1 唐晉韜;王挺;王戟;;適合復(fù)雜網(wǎng)絡(luò)分析的最短路徑近似算法[J];軟件學(xué)報(bào);2011年10期

2 張海濤;程蔭杭;;基于A*算法的全局路徑搜索[J];微計(jì)算機(jī)信息;2007年17期

，

本文編號(hào)：602777