[發明專利]一種圖數據處理的方法及裝置

有效

• 申請號: 201710061406.4
• 申請日: 2017-01-26
• 公開（公告）號: CN108364327B
• 公開（公告）日: 2021-09-17
• 發明（設計）人: 夏應龍;徐建;夏命榛
• 申請（專利權）人: 華為技術有限公司
• 主分類號: G06T11/20
• 分類號: G06T11/20
• 代理公司: 深圳市深佳知識產權代理事務所(普通合伙) 44285
• 代理人: 王仲凱

1.一種圖數據處理的方法，其特征在于，包括：

從數據庫中獲取圖數據，所述圖數據為包含K個域的多域圖，所述K個域中的每個域包含同一類型的至少兩個頂點，以及用于連接所述每個域內兩個頂點的至少一條域內邊，所述圖數據還包括用于連接屬于不同域的兩個頂點的至少一條域間邊，所述K≥2，且所述K為整數；

對所述圖數據進行轉換，以得到2K維的張量的1/2表面，所述2K維的張量為2K維的超立方體，所述每個域對應2個維度，所述張量的1/2表面包括相互正交的K(2K-1)個面，所述K(2K-1)個面中包括K個域內面和2K(K-1)個域間面，所述K個域內面中的每個域內面包括所述K個域中的一個域的所有域內邊，所述2K(K-1)個域間面中的每個域間面包括連接所述K個域中的兩個域的頂點的所有域間邊；

通過并行滑動窗口PSW從所述張量的1/2表面包含的每個面上，確定包含目標頂點的邊集合，所述目標頂點為所述每個面內所述PSW所覆蓋的頂點，所述邊集合用于圖數據處理。

2.根據權利要求1所述的方法，其特征在于，所述對所述圖數據進行轉換，以得到一個2K維的張量的1/2表面，包括：

將所述圖數據拆分為K個單域子圖和2K(K-1)個雙域子圖；

將每個單域子圖轉換為域內鄰接矩陣，將每個雙域子圖轉換為域間鄰接矩陣，其中，所述域內鄰接矩陣為以域內各頂點為行，再以所述域內各頂點為列所組成的矩陣形式的域內數據結構，所述每個域的各條域內邊分別位于所述域內數據結構中對應頂點的行和列的相交處；所述域間鄰接矩陣為以所述兩個域中的一個域的域內各頂點為行，另一個域的域內各頂點為列所組成的矩陣形式的域間數據結構，所述兩個域的各條域間邊分別位于所述域間數據結構中對應頂點的行和列的相交處；

按照所述域內鄰接矩陣和所述域間鄰接矩陣中表達相同域的行或列，對所述域內鄰接矩陣和所述域間鄰接矩陣進行拼接，以得到一個2K維的張量的1/2表面。

3.根據權利要求1或2所述的方法，其特征在于，所述通過并行滑動窗口PSW從所述張量的1/2表面包含的每個面上，確定包含目標頂點的邊集合，包括：

在所述K(2K-1)個面的每個面上滑動所述PSW，以確定所述每個面上包含所述目標頂點的邊集合，所述PSW包括由每個面上的水平數據帶和垂直數據帶聯合形成的高維空間數據區域，所述每個面上的垂直數據帶用于確定所述目標頂點的入邊的邊集合，所述水平數據帶用于確定所述目標頂點的出邊的邊集合，所述目標頂點為所述垂直數據帶所覆蓋的頂點。

4.根據權利要求3所述的方法，其特征在于，所述圖數據為超圖，所述超圖包括至少一條超邊，所述超邊為連接兩個以上頂點的邊。

5.根據權利要求4所述的方法，其特征在于，所述方法還包括：

對所述PSW進行泛化處理，以將所述每個面上的水平數據帶在除該水平數據帶所在維度的其它維度上延展到與所述水平數據帶所在面正交的其它面上，將所述垂直數據帶在除該垂直數據帶所在維度的其它維度上延展到與所述垂直數據帶所在面正交的其它面上；

滑動泛化后的PSW，以確定所述2K維的張量內部的邊集合。

6.根據權利要求1或2所述的方法，其特征在于，所述圖數據包括N條邊，當邊有方向時，所述N≥K(2K-1)，當邊無方向時，所述N≥K(K+1)/2，所述N為正整數；當邊無方向時，所述2K(K-1)個域間面中至多包含K(K-1)個有效面，所述有效面為從所述2K(K-1)個域間面中排除重復的域間面所得到的，且所述有效面為包含至少一條邊的域間面。