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

在審

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

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

本發(fā)明涉及一種查詢方法，特別涉及一種在分布式系統(tǒng)中處理大規(guī)模圖數(shù)據(jù)的子圖匹配的查詢方法，屬于數(shù)據(jù)庫(kù)和分布式圖分析處理領(lǐng)域。

背景技術(shù)

圖模型在很多領(lǐng)域有重要的應(yīng)用，如社交網(wǎng)絡(luò)、Web網(wǎng)絡(luò)、規(guī)劃問(wèn)題、生物信息等方面。隨著計(jì)算機(jī)、網(wǎng)絡(luò)的廣泛應(yīng)用，大量的圖模型數(shù)據(jù)也呈現(xiàn)指數(shù)級(jí)的增長(zhǎng)。2013年，facebook統(tǒng)計(jì)其每天新產(chǎn)生的數(shù)據(jù)量已達(dá)到500TB。與此同時(shí)，大多數(shù)圖模型處理的方法通常復(fù)雜度遠(yuǎn)高于O(n)，如，最常見(jiàn)的最短路方法，其最常見(jiàn)的方法floyd的計(jì)算復(fù)雜度是O(n^3)。在大規(guī)模的數(shù)據(jù)量下，單機(jī)處理這樣的計(jì)算復(fù)雜度是遠(yuǎn)遠(yuǎn)不能接受的。也就是說(shuō)，在大數(shù)據(jù)的背景下圖計(jì)算問(wèn)題大都要在分布式系統(tǒng)上進(jìn)行處理。

子圖匹配問(wèn)題由來(lái)已久，它在圖模型中有廣泛的應(yīng)用。比如化學(xué)分子結(jié)構(gòu)中的比對(duì)問(wèn)題、生物蛋白質(zhì)的匹配問(wèn)題，以及近年來(lái)最為廣泛的社交網(wǎng)絡(luò)中的模式匹配問(wèn)題等等。但是由于子圖匹配問(wèn)題本身是NP問(wèn)題，其問(wèn)題本身復(fù)雜度高、常見(jiàn)方法性能差，所以在很多領(lǐng)域的應(yīng)用中通常存在很大的效率問(wèn)題。其中尤以匹配順序、冗余的中間結(jié)果等引發(fā)的效率低下問(wèn)題最為普遍。

本發(fā)明處理的子圖匹配問(wèn)題是在有標(biāo)簽(label)的圖上進(jìn)行的，下面給出了問(wèn)題的相關(guān)定義。為了定義子圖匹配問(wèn)題，首先需要給出同構(gòu)圖的概念。

定義1同構(gòu)圖

給定圖G(V,E,L)和G₀(V₀,E₀,L₀)，這里V、V₀表示節(jié)點(diǎn)集，E、E₀表示邊集，L、L₀表示每個(gè)節(jié)點(diǎn)所屬的分類(標(biāo)簽)。如果存在映射F:V→V₀，對(duì)于L(v)＝L₀(F(v))，且對(duì)于則稱G和G₀是同構(gòu)的圖。

在本文中本發(fā)明統(tǒng)一使用u表示查詢圖節(jié)點(diǎn)，v表示數(shù)據(jù)圖節(jié)點(diǎn)，大寫(xiě)字母A-Z表示節(jié)點(diǎn)的分類(標(biāo)簽/label)。

定義2子圖匹配

子圖匹配問(wèn)題定義如下：給定數(shù)據(jù)圖G(V,E,L)，對(duì)于一個(gè)查詢圖Q(V′,E′,L′)，對(duì)于數(shù)據(jù)圖中的任意子圖G₀，若G₀和Q同構(gòu)，則G₀為子圖匹配的一個(gè)查詢結(jié)果。子圖匹配的目的是在數(shù)據(jù)圖G中找到所有和Q同構(gòu)的子圖。

可以發(fā)現(xiàn)，對(duì)于子圖匹配而言，對(duì)于大部分的查詢，其查詢結(jié)果都會(huì)非常的多。子圖匹配問(wèn)題也是經(jīng)證明后屬于NP的問(wèn)題，也就是說(shuō)即便數(shù)據(jù)圖很小，對(duì)于特定的查詢，全部結(jié)果的數(shù)據(jù)規(guī)模是不可接受的。為了更好的理解子圖匹配問(wèn)題，這里給出一些例子。例如，在有機(jī)高分子、蛋白質(zhì)中尋找相似的同構(gòu)子結(jié)構(gòu)；在社交網(wǎng)絡(luò)中尋找特定的模型用以數(shù)據(jù)挖掘；在程序的調(diào)用圖、流程圖里查找相似的模塊等等。

目前對(duì)于子圖匹配的方法主要可分為三類，其一是單機(jī)的方法，其方法主要思路是首先對(duì)查詢圖節(jié)點(diǎn)給出一個(gè)順序，接下來(lái)按照順序依次匹配，每匹配完一個(gè)節(jié)點(diǎn)后，根據(jù)情況遞歸匹配下一個(gè)查詢圖節(jié)點(diǎn)，直到能夠完整匹配全部的查詢圖節(jié)點(diǎn)。對(duì)于單機(jī)方法而言其本身的方法性能良好，但是對(duì)于處理大規(guī)模的數(shù)據(jù)圖存在很大的問(wèn)題。即當(dāng)判定特定數(shù)據(jù)邊是否存在的時(shí)候，因?yàn)閮?nèi)存無(wú)法存儲(chǔ)完整的數(shù)據(jù)圖，需要額外的訪問(wèn)外存或進(jìn)行網(wǎng)絡(luò)通信，這樣會(huì)造成很大的額外資源開(kāi)銷。

另一種方法是分布式方法，其中微軟提出的方法主要思路是首先將查詢圖拆分成由一個(gè)父節(jié)點(diǎn)和若干子節(jié)點(diǎn)的“小枝”結(jié)構(gòu)，然后在分布式的環(huán)境下對(duì)每個(gè)小枝進(jìn)行匹配，得到結(jié)果后進(jìn)行網(wǎng)絡(luò)通信，之后對(duì)中間結(jié)果進(jìn)行類似數(shù)據(jù)庫(kù)表連接的操作，最后得到完整的匹配結(jié)果。然而對(duì)于這種方法，其普遍存在小枝的順序問(wèn)題，即不同小枝順序會(huì)對(duì)查詢效率產(chǎn)生很大的影響。

另外，還可以將現(xiàn)有的單機(jī)方法與以節(jié)點(diǎn)為中心的分布式計(jì)算模型相結(jié)合。即對(duì)于每個(gè)查詢圖節(jié)點(diǎn)，在每一輪的迭代中進(jìn)行匹配，之后將中間結(jié)果發(fā)送給數(shù)據(jù)圖節(jié)點(diǎn)的鄰接點(diǎn)。但是這樣的實(shí)現(xiàn)存在迭代次數(shù)過(guò)多、中間結(jié)果較大、額外通信判定數(shù)據(jù)邊等問(wèn)題。最終導(dǎo)致其查詢結(jié)果效率較低。

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

本發(fā)明是為解決現(xiàn)有分布式子圖匹配方法查詢效率較低的問(wèn)題，提出了一種在分布式系統(tǒng)中處理大規(guī)模圖數(shù)據(jù)的子圖匹配的查詢方法。

首先，給出本發(fā)明所使用的相關(guān)定義。

定義3查詢樹(shù)