動態(tài)有向圖上面向最短路徑查詢的新型概要技術(shù)研究.pdf

1、近年來，隨著有向圖最短路徑查詢應(yīng)用在路網(wǎng)、計(jì)算機(jī)網(wǎng)絡(luò)和社交網(wǎng)絡(luò)等數(shù)據(jù)中的應(yīng)用不斷增加，有向圖的最短路徑查詢技術(shù)受到更加廣泛的關(guān)注?，F(xiàn)有技術(shù)可以高效的處理無向圖環(huán)境下的最短路徑查詢，然而由于有向圖上最短路徑查詢操作的特殊性使得在有向圖上的最短路徑查詢操作遇到了很大的挑戰(zhàn)，有向圖最短路徑查詢并無很好的解決方案。本文研究面向有向圖準(zhǔn)確的和帶有精度保證的最短路徑查詢信息概要技術(shù)，并提出動態(tài)圖環(huán)境下相應(yīng)概要增量維護(hù)算法。
　　首先，針對現(xiàn)有

2、有向圖最短路徑查詢技術(shù)在計(jì)算過程中在精度和速度上的缺陷，本文在代表點(diǎn)策略的基礎(chǔ)上提出基于生成樹編碼概要結(jié)構(gòu)，通過代表點(diǎn)策略降低內(nèi)存負(fù)載極大加快概要構(gòu)建速度和查詢速度;同時針對通過概要結(jié)構(gòu)覆蓋全部查詢概要結(jié)構(gòu)構(gòu)建過程中頻繁I/O的缺陷，改進(jìn)其磁盤索引結(jié)構(gòu)提出輕量級的概要結(jié)構(gòu);在證明準(zhǔn)確概要查詢結(jié)果有效性的前提下，本文提出了相應(yīng)的I/O高效構(gòu)建算法和查詢算法，并通過實(shí)驗(yàn)對準(zhǔn)確概要結(jié)構(gòu)性能進(jìn)行驗(yàn)證。其次，對于用戶要求在短時間內(nèi)獲取帶有誤差保證

3、最短距離的應(yīng)用請求，本文提出基于拓?fù)鋵拥碾x散landmark快速概要結(jié)構(gòu)，通過landmark節(jié)點(diǎn)的拓?fù)鋵哟魏拖嚓P(guān)信息，可以降低搜索數(shù)據(jù)大小并提前終結(jié)不必要的查詢，進(jìn)而加快查詢速度;針對查詢時在離散landmark節(jié)點(diǎn)集合搜索代價較大的缺陷，本文依照二分索引思想組織landmark節(jié)點(diǎn)構(gòu)建近似概要，并針對此概要結(jié)構(gòu)提出近似概要構(gòu)建算法和有精度保障的查詢算法;最終在真實(shí)數(shù)據(jù)集和模擬數(shù)據(jù)集上進(jìn)行大量的實(shí)驗(yàn)，驗(yàn)證近似概要結(jié)構(gòu)和相應(yīng)查詢算法的有

4、效性。最后，本文對概要結(jié)構(gòu)的高效查詢和動態(tài)圖環(huán)境下概要增量維護(hù)操作進(jìn)行研究，為了降低整體查詢代價以及動態(tài)圖環(huán)境下概要增量維護(hù)代價，本文設(shè)計(jì)離散磁盤結(jié)構(gòu)存儲Triad信息;同時在離散磁盤結(jié)構(gòu)的基礎(chǔ)上提出增量維護(hù)緩存結(jié)構(gòu)降低平均增量維護(hù)代價，并通過攤還分析證明緩存結(jié)構(gòu)的有效性;最后提出基于離散磁盤結(jié)構(gòu)信息獲取算法和增量維護(hù)算法，并通過實(shí)驗(yàn)證明其有效性。
　　本文從實(shí)際應(yīng)用中對有向圖最短路徑查詢的典型特征和調(diào)整進(jìn)行分析，針對有向圖最短路