[發(fā)明專利]一種圖上兩點間最短路徑查詢方法

有效

• 申請?zhí)枺?/td>: 201110421889.7
• 申請日: 2011-12-15
• 公開（公告）號: CN102521364A
• 公開（公告）日: 2012-06-27
• 發(fā)明（設計）人: 鄒磊;彭鵬;趙東巖;賈愛霞
• 申請（專利權）人: 北京大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京君尚知識產(chǎn)權代理事務所(普通合伙) 11200
• 代理人: 余長江

技術領域

本發(fā)明涉及數(shù)據(jù)庫技術和圖數(shù)據(jù)管理，主要涉及一種針對大規(guī)模圖的基于2-hop處理兩點間最短路徑查詢的軟件實現(xiàn)方法。

背景技術

圖數(shù)據(jù)庫是一種利用圖的結構和屬性來表示與存儲信息的新型數(shù)據(jù)庫技術，是NoSQL數(shù)據(jù)庫的一種。圖數(shù)據(jù)庫(graphic?database)是利用計算機將點、線、畫霹圖基本元素按一定數(shù)據(jù)結同灶行存儲的數(shù)據(jù)集合，將地圖與其它類型的平面圖中的圖描述為點、線、面等基本元素，并將這些圖元素按一定數(shù)據(jù)結構(通常為拓撲數(shù)據(jù)結構)建立起來的數(shù)據(jù)集合。包括兩個層次：第一層次為拓撲編碼的數(shù)據(jù)集合，由描述點、線、面等圖元素間關系的數(shù)據(jù)文件組成，包括多邊形文件、線段文件、結點文件等。文件間通過關聯(lián)數(shù)據(jù)項相互聯(lián)系；第二層次為坐標編碼數(shù)據(jù)集合，由描述各圖元素空間位置的坐標文件組成。圖數(shù)據(jù)庫仍是目前地理信息系統(tǒng)中對矢量結構地圖數(shù)字化數(shù)據(jù)進行組織的主要形式。一般的圖數(shù)據(jù)庫應該能存儲任何形式的圖，包括地理上的地圖、社會關系網(wǎng)絡等等。

圖數(shù)據(jù)庫是基于圖論的，它利用了圖論中點、邊等概念。其中，點常用來代表現(xiàn)實中的實體，如人、公司、賬戶及其他一切你希望記錄的事物。邊用來連接兩個點，用來表示兩點之間的關系。一般而言，點或邊上還會附帶其他信息。比如一個基于社交網(wǎng)絡的圖上，每個點代表一個人，那么這個點上不但包含有這人的名字，一般還會有諸如住址、聯(lián)系方式等其他信息，而邊上就可能會有兩個人具體關系的描述，比如父子關系、朋友關系等。

相較于傳統(tǒng)關系數(shù)據(jù)庫，圖數(shù)據(jù)庫能更為直接地映射到面向對象的應用中去，同時也能更自然地擴展到海量數(shù)據(jù)集上。圖數(shù)據(jù)庫不依賴于模式，所以它們也更適合于管理那些會經(jīng)常被更新的數(shù)據(jù)。

其中，最短路徑查詢是圖數(shù)據(jù)庫領域里極為重要的一項需求。例如，給定一個社交網(wǎng)絡圖，我們想了解兩個人之間的關系。顯然，我們可以將這兩個人在社交網(wǎng)絡圖中對應的點找到，之后，這就需要我們在大的社交網(wǎng)絡圖中找出連接這兩個點的路徑以表示二者的關系。

對于最短路徑查詢，現(xiàn)階段已經(jīng)有了不少的方法。但是，這些方法中有一些是基于迪杰斯特拉(Dijkstra)算法的改進，這些算法的查找效率有限；另外一些通過對圖上的點構建距離信息索引來提高路徑查詢的效率，但是現(xiàn)有的這些索引方法可擴展性都不強，無法滿足大數(shù)據(jù)量級的圖上路徑查詢需求。可見，傳統(tǒng)的圖數(shù)據(jù)庫技術已經(jīng)無法滿足日益增長的圖數(shù)據(jù)的應用的需求。

發(fā)明內容

本發(fā)明提出了一種基于2-hop的兩點間路徑查詢方法，用以對大規(guī)模圖數(shù)據(jù)上的最短路徑查詢進行高效地處理。

數(shù)據(jù)預處理主要是針對大規(guī)模圖數(shù)據(jù)及最短路徑查詢的特點設計的利用2-hop定義為圖構建索引并進行組織與存儲的方法。所謂2-hop，是在計算圖數(shù)據(jù)中兩點間距離時常用的一種數(shù)據(jù)結構。利用2-hop的定義，我們將給圖上每個點打上該點對應的hop信息，用來快速的計算兩點間的可達性或者距離。常見的hop信息計算方法就是找出兩點u和v之間最短路徑上一個點作為中心點，然后將u和v到中心點的距離信息分別記錄到u和v對應的hop信息中去。

本方法中，為了高效地計算構建索引，結合hop信息的定義，我們將hop信息分為兩類：基于中間性(Betweenness)定義的hop信息和基于圖分割技術的hop信息，我們并為其提出了新的計算方法。查詢執(zhí)行是針對本發(fā)明一種圖上兩點間最短路徑查詢方法，具體方法如下：

1)從圖上隨機抽取若干點作為支點，根據(jù)各支點間的最短路徑得出圖上每點的中間性估計值；

2)將中間性估計值大于設定值的點作為中心點，將圖中各點到各中心點的最短路徑信息加入圖中各點的hop信息，這些中心點的集合記為Wb；

3)將圖去除Wb中各點后分割為若干小圖Si，1＜i≤m，m為小圖個數(shù)，并得到點割集Ws；

4)對于每個小圖Si根據(jù)枚舉出的任意兩點間最短路徑，得到該小圖Si內的所有點的hop信息；

5)根據(jù)Wb中各點到Ws中各點的最短路徑得到不同小圖之間的點的hop信息；

6)根據(jù)圖中各點的hop信息，得到用戶輸入的兩查詢點之間的最短路徑。