[發明專利]一種并行環境下的有向圖可達性鏈表生成及查詢方法

有效

• 申請號: 201310317126.7
• 申請日: 2013-07-23
• 公開（公告）號: CN103399902A
• 公開（公告）日: 2013-11-20
• 發明（設計）人: 谷峪;王彪;于戈;鮑玉斌
• 申請（專利權）人: 東北大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 沈陽東大專利代理有限公司 21109
• 代理人: 梁焱

技術領域

本發明屬于大圖數據處理領域，特別涉及一種并行環境下的有向圖可達性鏈表生成及查詢方法。

背景技術

圖作為計算機領域的一種重要的數據結構，現今大量的信息處理應用圖作為數據結構，對圖的各種操作的需求不斷加大。圖的可達性查詢操作作為對圖的一種基本操作，在語義網絡、生物網絡和社交網絡中有重要應用，同時圖可達性也是一些對圖數據進行高級應用的基礎算法。對圖的可達性定義如下，對一個有向確定圖G，圖上的節點集合設為V，邊集合設為E，有向圖的可達性計算，是判斷一個有向確定圖的節點集合V中一個節點對（u,v）之間是否存在一條連通的路徑從u到v，如果存在，就返回true，否則就返回false。

已有的圖可達性處理技術主要應用與單處理機環境下圖的可達性計算，大多數都分成兩個步驟：圖可達性索引計算以及查詢計算，而并行環境下的圖可達性計算，都只是針對特定類型的圖數據，例如帶有標簽的圖或是帶有權值限制的圖可達性查詢，對于通常意義上的有向圖可達性查詢并無具體應用。

已有的涉及圖可達性查詢的計算方法主要有三類：第一種方法是壓縮傳遞閉包構建索引，如鏈索引、區間索引、二重索引、路徑樹索引以及比特向量索引。這些算法都只能處理小規模的圖數據，在數據量不斷增大的今天，僅僅能夠處理百萬節點千萬條邊的算法無法滿足實際應用。而如果強行使用磁盤存儲這些計算結果，任務的查詢時間遠遠超出可承受范圍甚至無法完成可達性查詢計算。

并行計算是將一個計算任務分配到多個處理機上分別完成，然后通過網絡通信進行數據傳輸，在這一過程中，傳輸的數據量是系統運行效率和擴展性的瓶頸；而且最終計算任務完成計算后，數據分配在各個處理機上，這時候查詢的速度就取決于一個查詢評價需要的數據量和通信次數。對于應用于單處理機環境的圖可達性查詢算法，在并行環境下，處理圖數據會導致大量冗余的網絡通信數據，以及更慢索引計算速度和查詢速度。

如果試圖將基于單個處理機的可達性計算方法在并行計算運行環境進行處理，突破單個處理機對大圖數據由于處理機性能的限制：內存中無法將整個圖全部讀入，或是無法將整個索引結構存在內存中完整放置。這些方法如果預計算代價較大，獲得結果涵蓋的可達性信息就相對更多，索引就更加詳細；則對應的查詢過程時間代價就相對較小，查詢計算速度就相對較快，但是這也會造成索引過大占用空間過多的問題。但是如果圖的更新操作過多，并且索引設計并不能增量維護圖的可達性索引，這種方案在預計算耗費的代價超出預期——每次進行更新就需要重新計算一次整個圖數據，計算的索引由于信息比較完備，通常與圖的邊成線性關系，計算代價大，索引存儲代價也較大；如果使用輕量級索引進行判斷，索引計算過程時間相對較短，但是查詢過程因為原有的索引并不能涵蓋整個圖上的數據，就需要對原圖的大量數據進行搜索。

發明內容

針對現有技術存在的不足，本發明的目的是提供一種基于關鍵節點壓縮結果，并在壓縮結果上使用基于跳表進行傳遞閉包壓縮的索引結構，在這個索引結構的基礎上，構建索引并根據索引進行可達性查詢判斷，達到了保證查詢結果的準確性、極大降低并行計算系統在查詢時的網路通信代價和查詢時間的目的。

本發明采用的技術方案是這樣實現的：一種并行環境下的有向圖可達性鏈表生成方法，包括以下步驟：

步驟1：首先將一個有向圖數據G分發到各個處理機中，每個處理機中存儲有圖中的節點及節點所對應的子節點；

步驟2：對分割到各個處理機內的圖數據進行壓縮，過程為：

步驟2-1：將所有與其他處理機有聯系的節點設為主干節點，所有主干節點經過k跳后所能到達的節點形成一個集合R；

步驟2-2：確定集合R的邊界節點經k跳后所能到達的節點形成另一個集合，依次計算該另一個集合中每個元素的評價函數，公式為：

r(C_x)=1/|C_x/R|

式中，r(C_x)表示評價函數，C_x為主干節點周圍k跳內的節點的集合，x表示待處理的節點，R為當前的主干節點集合的涵蓋范圍內節點集合；

該另一個集合中評價函數最大值所對應的節點確定為主干節點，此主干節點經過k跳后所能到達的節點均添加至集合R中，重復步驟2-2，直至集合R與有向圖數據G中的節點集合相同；

步驟2-3：各個處理器將經步驟2-2壓縮處理后的非主干節點信息存儲至磁盤上；