參考節點嵌入的圖可達性查詢算法
大小：1.36 MB 人氣：0 2017-12-15 需要積分：1
標簽：查詢算法(6333)
針對K步可達性查詢算法無法解決帶距離約束的圖可達性查詢問題，提出基于參考節點嵌入的圖可達性查詢算法。首先，從所有節點中選出極少數有代表性的全局參考節點，預先計算所有節點與全局參考節點之間的最短路徑距離；然后，采用最短路徑樹和范圍最小值查詢技術求得局部參考節點；接著，利用三角不等式關系得到查詢點對距離范圍；最后，根據查詢條件中的距離值與查詢點對距離范圍上、下限值的大小關系，可快速得出可達性結論。針對社會關系網絡和公路網絡數據，將所提算法與Dijkstra算法、K-Reach算法進行實驗對比測試。相較于K-Reach算法，其索引建立時間小4個數量級，其索引規模小2個數量級；相較于Dijkstra算法，在公路網絡和社會關系網絡中，直接得出可達性結論的比例分別為92%和78. 6%，其查詢時間大大縮短，分別降低了95. 5%和92%。實驗結果表明：所提算法能夠通過使用較小的索引開銷，實現在線查詢計算復雜度的降低，可很好地解決既適用于有權圖又適用于無權圖帶距離約束的可達性查詢問題。
非常好我支持^.^
(0) 0%
不好我反對
(0) 0%
