[發明專利]一種基于四維索引的大規模圖的可達查詢方法和系統

在審

• 申請號: 201710366030.8
• 申請日: 2017-05-23
• 公開（公告）號: CN107239515A
• 公開（公告）日: 2017-10-10
• 發明（設計）人: 袁平鵬;金海;周雙
• 申請（專利權）人: 華中科技大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 華中科技大學專利中心42201
• 代理人: 廖盈春,李智

技術領域

本發明屬于大數據處理技術領域，更具體地，涉及一種基于四維索引的大規模圖的可達查詢方法和系統。

背景技術

隨著大數據時代的到來，圖的規模也越來越大。圖查詢作為一種基礎性操作被應用于很多領域，比如社交網絡、運輸網絡、交通定位、基因的生物學功能分析和數據挖掘等。圖的可達性代表了圖上一個結點到另一個結點的能力，即是否存在一條以u為起始結點，以v為終止結點的路徑。

圖可達查詢有兩種極端的解決方法。第一種是基于預計算和存儲圖的完整傳遞閉包的方法，也就是預先記錄圖中任意兩個結點之間的可達性，該方法最早的研究工作可以追溯到1989年。這種方法的優點是查詢時間很快，時間復雜度是O(1)，但是該方法的缺點也很明顯，它需要O(|V|*|E|)的索引構建時間和O(|V|²)的索引存儲空間。第二種方法是采用深度優先遍歷或者廣度優先遍歷的方法來回答結點對的可達性，該方法雖然不需要構建索引，但是查詢時間的復雜度卻高達O(|V|+|E|)。因此，在大規模圖中，上述兩種方法都是不可行的。

目前，圖可達查詢的關鍵挑戰是在保證高效查詢時間的同時保證索引構建時間比較快和索引大小也比較有競爭力。到目前為止，很多研究者都研究了這個問題，但是隨著圖規模的增加，現有的方法都或多或少存在著問題，它們要么是索引構建時間太長，要么是索引太大，要么是查詢時間太慢。因此，如何在索引構建時間、索引大小和查詢時間三者之間找到一個平衡點是一個亟待解決的問題。

發明內容

針對現有技術的以上缺陷或改進需求，本發明提供了一種基于四維索引的大規模圖的可達查詢方法和系統，其目的在于通過對給定圖進行劃分，為每個結點構建一個四維索引來回答結點對的可達性，由此確保高效的查詢時間的同時保證索引構建時間和索引大小與現有方法相比都比較有競爭力。

為實現上述目的，按照本發明的一個方面，提供了一種基于四維索引的大規模圖的可達查詢方法，所述方法包括以下步驟：

(1)通過遞歸遍歷從目標圖中劃分出互不相交的不共享子圖和連接這些不共享子圖的跨子圖邊；結點的不共享子圖的編號為其所處不共享子圖所含根結點的編號，其層次索引按遞歸次數增加；

(2)由不共享子圖中所有結點的拓撲排序值求取該結點的間隔域，所述間隔域包括初始間隔域和目標間隔域；

(3)記錄所有不共享子圖中由于非樹邊的存在導致的不能使用間隔域判斷結點對可達性的異常情況；記錄所有不共享子圖中由于跨子圖邊的存在導致的不能直接判斷結點對可達性的異常情況；

(4)計算每個結點的向上等級索引和向下等級索引若結點u的出度為0，則u的上等級索引否則其中v為結點u的后繼鄰接點；若結點u的入度為0，則u的下等級索引否則其中v為結點u的前驅鄰接點；

(5)通過結點對的層次索引、所在不共享子圖編號、間隔域和等級索引的對比關系確定結點對的可達性。

進一步地，所述步驟(1)包括以下子步驟：

(11)找出目標圖G＝(V,E)中所有單根子圖M(r)＝(V_M(r),E_M(r))，單根子圖即目標圖中一個根結點能到達的所有結點和該根結點的集合，其中，V表示目標圖的結點；E表示目標圖的邊；r表示該單根子圖的根結點；V_M(r)表示單根子圖的結點；E_M(r)表示單根子圖的邊；

(12)在目標圖中找出所有位于兩個或兩個以上單根子圖中的結點V_U，由所有結點V_U和結點間相連的邊E_U構成共享子圖U＝(V_U,E_U)；

(13)構建不共享子圖為N(r)＝(V_N(r),E_N(r))，其中，E_N(r)＝{(u,v)|u∈V_N(r),v∈V_N(r),(u,v)∈E}；并將該不共享子圖中所有結點的層次索引賦值為1，不共享子圖編號賦值為不共享子圖的根結點ID；