[發明專利]一種輕量級的高效圖頂點重排方法

在審

• 申請號: 202011134445.0
• 申請日: 2020-10-21
• 公開（公告）號: CN112380397A
• 公開（公告）日: 2021-02-19
• 發明（設計）人: 劉志丹;黃保福;伍楷舜
• 申請（專利權）人: 深圳大學
• 主分類號: G06F16/901
• 分類號: G06F16/901;G06F17/16
• 代理公司: 廣州粵高專利商標代理有限公司 44102
• 代理人: 張金福

本發明涉及一種輕量級的高效圖頂點重排方法，所述方法包括以下步驟：S1：加載需進行ID重排的圖，并進行預處理，確定種子點；S2：選擇種子點，并通過種子點生成超頂點；S3：根據超頂點為需進行ID重排的圖的頂點分配新ID，從而實現圖頂點重排。本發明通過合并低入度頂點再分配ID的方法，使得合并頂點的共同鄰居擁有相近的ID。由于本發明在進行ID重排時總是依據當前頂點直接相連的頂點信息，屬于局部信息，在實現局部最優的同時追求快速完成重排操作，故本發明的重排操作亦是高效的，可有效圖提高圖頂點重排效率。

技術領域

本發明涉及圖計算領域，更具體地，涉及一種輕量級的高效圖頂點重排方法。

背景技術

由于圖能夠很好地表示現實的各種關系，并且可以通過各種圖算法來發挖掘圖結構中潛在的事實，故圖計算有很多應用。然而，大規模圖譜的計算需要操作的數據量非常大，為了更高效地完成圖計算，學者試圖從多個方面進行優化，包括圖計算環境的完善、算法層面的優化以及圖數據的預處理等方面。其中圖數據的預處理在圖算法執行之前，不涉及具體圖算法，不需要對原有算法進行修改，故某一確定圖經過一次預處理后，可以在新圖上進行不同圖算法的單次或者多次計算。

以上的圖計算預處理方法具體指對圖頂點ID重新進行分配方法。用圖結構表示現實關系時，需要為每個圖頂點分配一個唯一的ID，便于圖的存儲與圖計算。圖計算主要包括鄰居信息獲取與本地計算兩個階段，頂點需要獲取其鄰居的信息，具體地是通過邊表獲取其鄰居的ID，進而訪問該ID所對應的數據。具體應用上，常常使用數組來按序存儲所有頂點的數據，頂點的ID對應數組的下標，可通過數組+ID直接訪問該頂點的數據。對數組元素的訪問分為順序訪問方式和不規則訪問方式，兩者在數據的訪問效率上差異較大。順序訪問方式可以很好地利用空間局部性原理，以提高cache的命中率，從而加快計算速度，故應該盡最大可能實現對數組的訪問是按序。此外，數組中高頻訪問的元素應該常駐cache，以獲得更多數據訪問的時間局部性效益，加快計算速度。

在圖頂點ID重排方面已有較廣較深入的研究，根據不同方法完成重排所需要消耗的時間長短可分為耗時型與輕量級ID重排方法。經某ID重排方法得到圖頂點新ID，如果在該新圖上完成相同圖計算所需的時間相對原圖更少，則稱該方法的重排結果是高效的，否則是低效的；如果該方法完成重排所需要的時間遠大于圖算法的計算時間，則稱該方法的重排操作是低效的，稱為耗時型ID重排方法，否則是高效的，稱為輕量級ID重排方法。

耗時型ID重排方法以Gorder(H.Wei,J.X.Yu,C.Lu,and X.Lin.Speedup graphprocessing by graph ordering.In ACM SIGMOD,2016.)為代表。Gorder通過分析給出，結構上相鄰的頂點應該擁有相近的ID，即擁有許多共同鄰居的頂點，它們ID應該是相近的。形式描述如等式①，第一部分表示頂點u與頂點v的共同鄰居個數，取值為共同鄰居總個數，第二部分表示頂點u與v是否為鄰居頂點，取值為1或者0。Gorder為頂點分配新ID時追求F(Φ)的最大化，可得較高效的重排結果，其中F(Φ)由等式②計算所得。但是Gorder亦說明，最小化F(Φ)是一個NP難問題，在大規模的圖數據上直接使用該法進行重排，所需要的重排時間很長，重排操作是低效的，不適用于實際應用，故Gorder提出一種近似計算方法來進行重排，其重排思想與最大化F(Φ)是一致的，故其重排效果也是高效的，但是其重排操作仍然是低效的。

S(u,v)＝S_s(u,v)+S_n(u,v) ①