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

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

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