[發(fā)明專利]基于強(qiáng)模擬的圖模式匹配方法、裝置及系統(tǒng)

有效

• 申請(qǐng)?zhí)枺?/td>: 201110402608.3
• 申請(qǐng)日: 2011-12-06
• 公開(kāi)（公告）號(hào): CN102521332A
• 公開(kāi)（公告）日: 2012-06-27
• 發(fā)明（設(shè)計(jì)）人: 馬帥;曹洋;樊文飛;沃天宇;胡春明;懷進(jìn)鵬
• 申請(qǐng)（專利權(quán)）人: 北京航空航天大學(xué)
• 主分類(lèi)號(hào): G06F17/30
• 分類(lèi)號(hào): G06F17/30
• 代理公司: 北京同立鈞成知識(shí)產(chǎn)權(quán)代理有限公司 11205
• 代理人: 劉芳

技術(shù)領(lǐng)域

本發(fā)明涉及數(shù)據(jù)庫(kù)搜索技術(shù)，尤其涉及一種基于強(qiáng)模式的圖模式匹配方法、裝置及系統(tǒng)，屬于數(shù)據(jù)庫(kù)技術(shù)領(lǐng)域。

背景技術(shù)

圖模式匹配又稱為圖模式查詢，已經(jīng)廣泛應(yīng)用到社交網(wǎng)絡(luò)關(guān)系挖掘、生物數(shù)據(jù)庫(kù)、軟件剽竊檢測(cè)以及智能信息分析處理等技術(shù)領(lǐng)域，在這些應(yīng)用中，數(shù)據(jù)不僅僅是單一的實(shí)體，數(shù)據(jù)之間的聯(lián)系也同等重要，圖作為一種既能表達(dá)數(shù)據(jù)、又能表達(dá)數(shù)據(jù)之間聯(lián)系的新型數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)被應(yīng)用到上述領(lǐng)域中，并可被稱為圖數(shù)據(jù)。

圖模式匹配是對(duì)這種圖數(shù)據(jù)的查詢和檢索操作，一般而言，圖模式是從應(yīng)用中抽象出的一組對(duì)圖數(shù)據(jù)的約束，這種約束表達(dá)成一個(gè)模式圖，該模式圖的節(jié)點(diǎn)和邊上均可攜帶對(duì)所查詢圖數(shù)據(jù)的語(yǔ)義約束，其中利用節(jié)點(diǎn)代表數(shù)據(jù)本身，而邊代表數(shù)據(jù)之間的聯(lián)系。圖模式匹配即是在給定圖數(shù)據(jù)和查詢模式圖的情況下，在圖數(shù)據(jù)(一般非常大)中查詢出有若干節(jié)點(diǎn)(數(shù)據(jù))和邊(數(shù)據(jù)之間的聯(lián)系)組成的數(shù)據(jù)子圖，使得該數(shù)據(jù)子圖符合查詢模式圖所表達(dá)的約束，即找到模式圖中節(jié)點(diǎn)到該數(shù)據(jù)子圖中節(jié)點(diǎn)的匹配映射，以及模式圖中的邊到該數(shù)據(jù)子圖中的邊的匹配映射。

目前的圖模式匹配方法中，有一種基于子圖同構(gòu)(subgraph?isomorphism)的匹配方法，其匹配是由模式圖的節(jié)點(diǎn)集合和邊集合到數(shù)據(jù)子圖的節(jié)點(diǎn)集合和邊集合一一映射確定，子圖同構(gòu)所表達(dá)的約束過(guò)于嚴(yán)格，其要求模式圖到數(shù)據(jù)圖的匹配是點(diǎn)到點(diǎn)、邊到邊一一映射，這種嚴(yán)格的語(yǔ)義約束往往會(huì)使查詢結(jié)果遺漏應(yīng)用所要求的匹配結(jié)果，無(wú)法找全所需信息。

現(xiàn)有技術(shù)中的上述兩種圖模式匹配方法，無(wú)法在提高效率的同時(shí)增加圖模式匹配的準(zhǔn)確率。

發(fā)明內(nèi)容

本發(fā)明提供一種用于實(shí)現(xiàn)高效而準(zhǔn)確進(jìn)行圖模式匹配的基于強(qiáng)模擬的圖模式匹配方法、裝置及系統(tǒng)，能夠在提高圖模式匹配效率的同時(shí)提供其準(zhǔn)確率。

本發(fā)明的一個(gè)方面提供一種基于強(qiáng)模擬的圖模式匹配方法，包括：

獲取匹配模式圖和數(shù)據(jù)圖；

以所述數(shù)據(jù)圖的各個(gè)節(jié)點(diǎn)為球心，以所述匹配模式圖的直徑為半徑建立匹配球體；

根據(jù)對(duì)偶模擬的約束條件分別對(duì)所有的所述匹配球體進(jìn)行匹配處理，以獲取所述匹配模式圖和各個(gè)匹配球體中的對(duì)偶模式關(guān)系集合，所述對(duì)偶模擬約束條件為匹配模式圖中的節(jié)點(diǎn)與其在匹配球體中的對(duì)偶匹配節(jié)點(diǎn)的類(lèi)型相同，所述匹配球體中存在所述匹配模式圖中的節(jié)點(diǎn)的父代節(jié)點(diǎn)的對(duì)偶匹配節(jié)點(diǎn)，所述匹配球體中存在所述匹配模式圖中的節(jié)點(diǎn)的子代節(jié)點(diǎn)的對(duì)偶匹配節(jié)點(diǎn)；

根據(jù)所述對(duì)偶模式關(guān)系集合，獲取所有所述匹配球體中的匹配子圖，所述匹配子圖中包括其所在的匹配球體的球心。

本發(fā)明另一個(gè)方面提供一種基于強(qiáng)模擬的圖模式匹配裝置，包括：

獲取模塊，用于獲取匹配模式圖和數(shù)據(jù)圖；

匹配球體建立模塊，用于以所述數(shù)據(jù)圖的各個(gè)節(jié)點(diǎn)為球心，以所述匹配模式圖的直徑為半徑建立匹配球體；

匹配處理模塊，用于根據(jù)對(duì)偶模擬的約束條件分別對(duì)所有的所述匹配球體進(jìn)行匹配處理，以獲取所述匹配模式圖和各個(gè)匹配球體的對(duì)偶模式關(guān)系集合，所述對(duì)偶模擬約束條件為匹配模式圖中的節(jié)點(diǎn)與其在匹配球體中的對(duì)偶匹配節(jié)點(diǎn)的類(lèi)型相同，所述匹配球體中存在所述匹配模式圖中的節(jié)點(diǎn)的父代節(jié)點(diǎn)的對(duì)偶匹配節(jié)點(diǎn)，所述匹配球體中存在所述匹配模式圖中的節(jié)點(diǎn)的子代節(jié)點(diǎn)的對(duì)偶匹配節(jié)點(diǎn)；

匹配子圖生成模塊，用于根據(jù)所述對(duì)偶模式關(guān)系集合，獲取所有所述匹配球體中的匹配子圖，所述匹配子圖中包括其所在的匹配球體的球心。

本發(fā)明的再一個(gè)方面提供一種基于強(qiáng)模擬的圖模式匹配系統(tǒng)，包括一個(gè)主處理設(shè)備，以及一臺(tái)以上的從處理設(shè)備；所述主處理設(shè)備用于獲取匹配模式圖和數(shù)據(jù)圖，并將所述數(shù)據(jù)圖劃分為兩個(gè)以上的數(shù)據(jù)子圖，所述兩個(gè)以上的數(shù)據(jù)子圖與從處理設(shè)備和主處理設(shè)備一一對(duì)應(yīng)；

所述主處理設(shè)備還用于將所述匹配模式圖，以及對(duì)應(yīng)的數(shù)據(jù)子圖發(fā)送給從處理設(shè)備，以及用于以對(duì)應(yīng)的數(shù)據(jù)子圖的各個(gè)節(jié)點(diǎn)為球心，以所述匹配模式圖的直徑為半徑建立匹配球體，并根據(jù)對(duì)偶模擬的約束條件分別對(duì)建立的匹配球體進(jìn)行匹配處理，以獲取所述匹配模式圖和各個(gè)匹配球體的對(duì)偶模式關(guān)系集合；以及根據(jù)所述對(duì)偶模式關(guān)系集合，獲取匹配球體中的匹配子圖；

所述一臺(tái)以上的從處理設(shè)備用于以對(duì)應(yīng)的數(shù)據(jù)子圖的各個(gè)節(jié)點(diǎn)為球心，以所述匹配模式圖的直徑為半徑建立匹配球體，并根據(jù)對(duì)偶模擬的約束條件分別對(duì)建立的匹配球體進(jìn)行匹配處理，以獲取所述匹配模式圖和各個(gè)匹配球體的對(duì)偶模式關(guān)系集合，以及用于根據(jù)所述對(duì)偶模式關(guān)系集合，獲取匹配球體中的匹配子圖，并將獲取的匹配子圖發(fā)送所述主處理設(shè)備。