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