大規(guī)模圖的最短距離索引構建方法研究.pdf

1、伴隨著大數(shù)據(jù)時代的到來，圖處理面臨的數(shù)據(jù)規(guī)模越來越大，使得傳統(tǒng)的距離算法(Dijkstra, BFS, Floyd)因為內(nèi)存瓶頸變得不再適用，同時在在線應用中，對響應時間要求高，傳統(tǒng)算法會因運算時間過長而無法滿足實時響應的需求。
　　為滿足現(xiàn)實應用中對距離查詢的實時響應要求，基于索引的大規(guī)模圖最短距離查詢算法得以提出。這本質(zhì)上是一種空間換時間的策略?；谒饕牟樵兯惴ò瑑蓚€階段，即構建索引階段和距離查詢階段。構建索引是一個離線計

2、算的過程，通過預處理計算出圖中部分頂點間的距離并以文件的形式存于磁盤；距離查詢是一個在線過程，給出查詢的兩個頂點，通過前面預計算的索引組合計算出距離。如何構建索引，使得索引的預處理時間盡量短，占用空間盡量小及相應的查詢算法盡量簡單是解決這類問題的關鍵因素。
　　針對動態(tài)圖的索引增量式更新方法，可以在頂點不變，增加新邊的情況下，利用“打補丁”的方式更新現(xiàn)有索引，避免了重新構造索引的復雜計算過程，測試結果表明這種方法可有效節(jié)約時間。<