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

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

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

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