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

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

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

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

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