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