[發(fā)明專利]一種子圖匹配的查詢方法

在審

• 申請?zhí)枺?/td>: 201410812269.X
• 申請日: 2014-12-23
• 公開（公告）號: CN104392010A
• 公開（公告）日: 2015-03-04
• 發(fā)明（設(shè)計）人: 金福生;楊藝峰;顏震;薛野;韓翔宇
• 申請（專利權(quán)）人: 北京理工大學(xué)
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種子圖匹配的查詢方法,其特征在于：包括以下步驟：?

步驟一、修改查詢圖為查詢樹；?

步驟二、數(shù)據(jù)圖節(jié)點按照查詢樹從葉節(jié)點到根節(jié)點逐層依次匹配，得到匹配計數(shù)，并發(fā)送計數(shù)給相鄰節(jié)點，直到匹配根節(jié)點；?

步驟三、數(shù)據(jù)圖節(jié)點按照查詢樹從根節(jié)點到葉節(jié)點逐層依次發(fā)送匹配要求，直到匹配要求發(fā)送至葉節(jié)點；?

步驟四、數(shù)據(jù)圖節(jié)點按照查詢樹從葉節(jié)點到根節(jié)點的順序依次向查詢要求的來源發(fā)送子樹匹配結(jié)果。?

2.根據(jù)權(quán)利要求1所述的一種子圖匹配的查詢方法，其特征在于：所述修改查詢圖為查詢樹進一步包括以下過程：?

[1]枚舉所有節(jié)點作為樹的根節(jié)點；?

[2]使用廣度遍歷方法獲得當(dāng)前根節(jié)點對應(yīng)的查詢樹；?

[3]對于生成的所有候選查詢樹，根據(jù)下式選取其中估值最小(首先選擇通信量估值最小，其次選擇計算量估值最小)的作為最終查詢樹；其中通信量估值計算公式如下：?

計算量估值計算公式如下：?

其中deg表示數(shù)據(jù)圖節(jié)點的平均度數(shù)，cnt(u)表示查詢樹中節(jié)點u和第i個查詢節(jié)點的距離，keyset_i表示以第i個查詢節(jié)點為根的查詢子樹的關(guān)鍵節(jié)點集，child_i表示以第i個查詢節(jié)點為根的查詢子樹的子節(jié)點集，n為查詢圖中的節(jié)點個數(shù)。?

3.根據(jù)權(quán)利要求2所述的一種子圖匹配的查詢方法，其特征在于：所述使用廣度遍歷方法獲得當(dāng)前根節(jié)點對應(yīng)的查詢樹進一步包括以下過程：?

[1]使用邊的訪問集evis來表示某一條邊(u,v)是否被加入樹中，使用點的訪問集nvis來表示節(jié)點是否被訪問過，使用先進先出隊列q作為廣度遍歷的隊列；?

[2]將查詢樹根節(jié)點加入隊列q；?

[3]取出隊首節(jié)點u，依次枚舉其鄰接點v；?

[4]如果邊(u,v)已經(jīng)在樹中，則跳過邊(u,v)；?

[5]如果邊(u,v)不在樹中，且節(jié)點v已經(jīng)被訪問過，則將節(jié)點v拆分出節(jié)點v`加入樹中；?

[6]如果邊(u,v)不在樹中，且節(jié)點v未被訪問過，則將v直接加入樹中，并標(biāo)記v為已訪問，且將v加入隊列q；?

[7]若隊列為空，算法結(jié)束；否則，轉(zhuǎn)到[3]。?

4.根據(jù)權(quán)利要求1所述的一種子圖匹配的查詢方法，其特征在于：對所述數(shù)據(jù)圖節(jié)點按照查詢樹自下而上的方向傳遞匹配結(jié)果計數(shù)進一步包含以下步驟：?

[1]輸入數(shù)據(jù)圖到分布式集群中，每個機器存儲一部分的子圖；跨機器的鄰接點間使用網(wǎng)絡(luò)通信，其他的節(jié)點間使用內(nèi)存通信；?

[2]獲得查詢樹高度-1層節(jié)點的label集合；?

[3]選擇符合label集合的數(shù)據(jù)節(jié)點作為計算節(jié)點集合；?

[4]i＝1,N＝查詢樹高度，根節(jié)點高度為1；?

[5]對所有分布式集群中的計算節(jié)點v并行執(zhí)行如下過程；?

[6]在i不為1的時候，計算節(jié)點v接受相鄰數(shù)據(jù)節(jié)點發(fā)送過來的匹配查詢樹第N-i+1層查詢節(jié)點所代表子樹的匹配結(jié)果；?

[7]計算節(jié)點v根據(jù)v的鄰接表匹配查詢樹第N-i層查詢節(jié)點的獨立子節(jié)點；?

[8]計算節(jié)點v根據(jù)接收到的匹配結(jié)果匹配查詢樹第N-i層查詢節(jié)點的非獨立子節(jié)點；?

[9]將獨立、非獨立子節(jié)點的匹配結(jié)果進行數(shù)據(jù)庫表自然連接操作得到第N-i層查詢節(jié)點的匹配結(jié)果；?

[10]判斷當(dāng)前的結(jié)果是否已經(jīng)匹配查詢樹根節(jié)點，如果匹配，結(jié)束計算；?

[11]不匹配，將中間結(jié)果經(jīng)關(guān)鍵節(jié)點計數(shù)得到索引計數(shù)，發(fā)送給相鄰數(shù)據(jù)節(jié)點，并設(shè)置其為下一輪迭代中的計算節(jié)點；?

[12]數(shù)據(jù)節(jié)點計算線程同步，i++，轉(zhuǎn)到[5]。?