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