[發明專利]一種基于鄰接節點樹的網絡圖索引方法

無效

• 申請號: 201210063543.9
• 申請日: 2012-03-12
• 公開（公告）號: CN102662974A
• 公開（公告）日: 2012-09-12
• 發明（設計）人: 貝毅君;徐俊;干紅華;劉二騰
• 申請（專利權）人: 浙江大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 杭州天勤知識產權代理有限公司 33224
• 代理人: 胡紅娟

1.一種基于鄰接節點樹的網絡圖索引方法，包括步驟：

(1)、根據網絡圖節點間的鄰接關系，建立網絡圖的鄰接節點樹索引，根據查詢圖節點間的鄰接關系，分解查詢圖；

(2)、將網絡圖中與查詢圖節點標簽相同的節點集合作為查詢圖節點的初始匹配候選集；

(3)、通過剪枝獲得每一個查詢圖節點對應的節點匹配候選集；

(4)、采用鄰接節點樹集的覆蓋策略實現子圖匹配。

2.如權利要求1所述的基于鄰接節點樹的網絡圖索引方法，其特征在于，所述步驟(1)包括步驟：

將網絡圖的鄰接點樹進行模式標準化，根據圖節點間的鄰接關系分別建立網絡圖和查詢圖的標簽表、逐層特征表以及邊列表，并以此為基礎構建網絡圖鄰接節點樹索引；

將查詢圖的鄰接點樹進行模式標準化，根據圖節點間的鄰接關系分別建立網絡圖和查詢圖的標簽表、逐層特征表以及邊列表。

3.如權利要求2所述的基于鄰接節點樹的網絡圖索引方法，其特征在于：所述將鄰接點樹進行模式標準化是采用深度優先方法。

4.如權利要求3所述的基于鄰接節點樹的網絡圖索引方法，其特征在于：所述模式標準化是指使用樹字符串方式表示鄰接節點樹。

5.如權利要求2所述的基于鄰接節點樹的網絡圖索引方法，其特征在于：采用廣度優先方法，建立網絡圖和查詢圖的標簽表、逐層特征表以及邊列表。

6.如權利要求5所述的基于鄰接節點樹的網絡圖索引方法，其特征在于：所述標簽表、逐層特征表以及邊列表為哈希表。

7.如權利要求2所述的基于鄰接節點樹的網絡圖索引方法，其特征在于，v是查詢圖中的節點，u是節點v的初始匹配候選集中的節點，所述步驟(3)包括步驟：

3.1)、比較v和u的相鄰節點標簽表，設節點v的中有標簽為X的鄰接節點數為n_v，如果節點u沒有標簽為X的鄰接節點或者鄰接節點數小于n_v，則從初始匹配候選集中剔除u，并轉入步驟3.4)，否則，繼續下面步驟3.2)；

3.2)、查詢節點v和u的逐層特征表，比較相同層邊的數量，設邊相對于節點v和u的層為k時，具有某相同邊e的數量分別為count(e，v)、count(e，u)，如果count(e，v)小于count(e，u)，則從初始匹配候選集中剔除u，并轉入步驟3.4)，否則，繼續下面步驟3.3)；

3.3)、比較節點v和u鄰接節點樹的字符串，如果節點u的字符串不能包含節點v的字符串，則從初始匹配候選集中剔除u；

3.4)、若初始匹配候選集中還有未訪問過的節點則轉入步驟3.1)，遍歷初始匹配候選集中每一個節點，否則結束。

8.如權利要求7所述的基于鄰接節點樹的網絡圖索引方法，其特征在于，所述步驟4)包括步驟：

選擇查詢圖中的一個節點v’作為第一個要訪問的節點，遍歷v’的節點匹配候選集，用集合I存放網絡圖和查詢圖中當前已匹配的鄰接節點樹，u’為節點匹配候選集中的節點，如果滿足如下條件：

(1)u’的鄰接節點樹T(u’)與網絡圖中已匹配的某鄰接節點樹P相交；

(2)v’的鄰接節點樹T(v’)與查詢圖中已匹配的某鄰接節點樹P’相交；

(3)P與P’已經匹配，則認為T(u’)和T(v’)匹配，并將T(u’)和T(v’)放入集合I，并標記T(v’)中包含的查詢圖的邊為已訪問；

當查詢圖的所有邊都已訪問，集合I中網絡圖已匹配的所有鄰接節點樹所構成的網絡子圖即為一個查詢結果；

當v’的節點匹配候選集中所有節點均已訪問，則查詢結束，并返回所有獲得的查詢結果。

9.如權利要求8所述的基于鄰接節點樹的網絡圖索引方法，其特征在于，其中相交是指樹與樹之間至少存在一條共有的邊。