[發(fā)明專(zhuān)利]一種Spark并發(fā)子圖查詢(xún)的方法

在審

• 申請(qǐng)?zhí)枺?/td>: 201711346701.0
• 申請(qǐng)日: 2017-12-15
• 公開(kāi)（公告）號(hào): CN108090179A
• 公開(kāi)（公告）日: 2018-05-29
• 發(fā)明（設(shè)計(jì)）人: 王明興
• 申請(qǐng)（專(zhuān)利權(quán)）人: 北京海致星圖科技有限公司
• 主分類(lèi)號(hào): G06F17/30
• 分類(lèi)號(hào): G06F17/30
• 代理公司: 暫無(wú)信息
• 代理人: 暫無(wú)信息

1.一種Spark并發(fā)子圖查詢(xún)的方法，其特征在于：包括以下步驟：

S1：生成查詢(xún)圖的查詢(xún)計(jì)劃，將其拆分成多個(gè)查詢(xún)子圖，每個(gè)查詢(xún)子圖包含1條或多條邊，所有的邊包含一個(gè)公共的頂點(diǎn)；

S2：數(shù)據(jù)圖數(shù)據(jù)預(yù)處理，原始數(shù)據(jù)圖給出了每個(gè)頂點(diǎn)和邊的屬性值，查詢(xún)子圖中給出了頂點(diǎn)和邊的匹配函數(shù)，預(yù)處理過(guò)程中先判斷數(shù)據(jù)圖中每個(gè)頂點(diǎn)與查詢(xún)子圖中哪些頂點(diǎn)匹配，數(shù)據(jù)圖中的每條邊與查詢(xún)子圖中哪些邊匹配；

S3：從查詢(xún)計(jì)劃中取第一個(gè)查詢(xún)子圖，計(jì)算匹配實(shí)例和匹配點(diǎn)集；

S4：依次從查詢(xún)計(jì)劃中取下一個(gè)查詢(xún)子圖，計(jì)算該查詢(xún)子圖的匹配實(shí)例和匹配點(diǎn)集，將其與之前的匹配結(jié)果合并；

S5：查詢(xún)計(jì)劃執(zhí)行完成后輸出最終的匹配結(jié)果。

2.根據(jù)權(quán)利要求1所述的一種Spark并發(fā)子圖查詢(xún)的方法，其特征在于：根據(jù)步驟S1，所述查詢(xún)圖拆分包括以下步驟：

A1：取度數(shù)最大的頂點(diǎn)作為查詢(xún)子圖的根節(jié)點(diǎn)，所有與根節(jié)點(diǎn)相連的邊與點(diǎn)構(gòu)成一個(gè)新的查詢(xún)子圖，度數(shù)最大的頂點(diǎn)存在多個(gè)時(shí)可隨機(jī)選一個(gè)；

A2：從查詢(xún)圖刪除相應(yīng)的邊，邊刪除后如果存在孤立的頂點(diǎn)也刪除，按步驟A1的方式生成新的查詢(xún)子圖；

A3：如果此查詢(xún)子圖與之前生成的查詢(xún)子圖的頂點(diǎn)有交集，則此查詢(xún)子圖是合法的，否則排除此查詢(xún)子圖的根節(jié)點(diǎn)，按步驟A1的方式生成新的查詢(xún)子圖，直到生成滿(mǎn)足條件的查詢(xún)子圖；

A4：當(dāng)所有邊都屬于某個(gè)查詢(xún)子圖時(shí)終止。

3.根據(jù)權(quán)利要求2所述的一種Spark并發(fā)子圖查詢(xún)的方法，其特征在于：所述度數(shù)為連接的邊的數(shù)量。

4.根據(jù)權(quán)利要求1所述的一種Spark并發(fā)子圖查詢(xún)的方法，其特征在于：根據(jù)步驟S2，

所述頂點(diǎn)匹配判定用一個(gè)BitSet來(lái)記錄數(shù)據(jù)圖中的頂點(diǎn)匹配哪些查詢(xún)圖中的頂點(diǎn)，假設(shè)查詢(xún)圖中頂點(diǎn)的數(shù)量為numQv，spark并行匹配方法為：

val graphVertexMatch = dataGraph.mapVertices((_, vd) => { val bitSet =new BitSet(numQv) checkVertexMatch(bitSet) bitSet})

圖graphVertexMatch中每個(gè)頂點(diǎn)的屬性記錄該頂點(diǎn)與查詢(xún)圖中的哪些頂點(diǎn)匹配；

所述邊匹配判定，一條邊匹配查詢(xún)圖中的邊需同時(shí)滿(mǎn)足邊的屬性匹配以及兩端頂點(diǎn)屬性匹配，得到頂點(diǎn)屬性匹配結(jié)果后，判定數(shù)據(jù)圖中的每條邊與查詢(xún)圖中的哪些邊匹配，假設(shè)查詢(xún)圖中邊的數(shù)量為numQe ,spark并行匹配方法為：

val graphTriplets = graphVertexMatch mapEdges(e => { val bitSet = newBitSet(numQe) checkEdgeMatch(bitSet) bitSet}) triplets map(et => matchTriplet(et)) filter(et => et.attr.size > 0)

其中matchTriplet 為邊的3元組匹配方法，假設(shè)查詢(xún)圖第i條邊的起始點(diǎn)為srci，目標(biāo)點(diǎn)為dsti：

若考慮邊的方向，et滿(mǎn)足查詢(xún)圖第i條邊的條件為：

et的邊屬性滿(mǎn)足i，且j的起始點(diǎn)匹配srci，目標(biāo)點(diǎn)匹配dsti；

若不考慮邊的方向，匹配條件為：

et的邊屬性滿(mǎn)足i，且et的起始點(diǎn)匹配srci，目標(biāo)點(diǎn)匹配dsti，或et的目標(biāo)點(diǎn)匹配srci，起始點(diǎn)匹配dsti；

判定邊的匹配后可從結(jié)果中過(guò)濾掉與查詢(xún)圖任何邊都不匹配的邊，如上述匹配方法中的最后一行：

filter(et => et.attr.size > 0)

過(guò)濾后的結(jié)果graphTriplets（3元組）作為后續(xù)計(jì)算的輸入。