Jin T, Li B, Li Y, et al. Circinus: Fast redundancy-reduced subgraph matching[J]. Proceedings of the ACM on Management of Data, 2023, 1(1): 1-26.

1 INTRODUCTION

子圖匹配是圖分析中的一個(gè)基本問(wèn)題，它具有廣泛的應(yīng)用領(lǐng)域，如生物信息學(xué)[27]、化學(xué)[45]、金融[5]和社會(huì)網(wǎng)絡(luò)分析[35]。給定一個(gè)數(shù)據(jù)圖??和一個(gè)查詢(xún)圖??，其中??和??中的頂點(diǎn)可以被標(biāo)記或不標(biāo)記，子圖匹配的問(wèn)題是找到??的所有與??同構(gòu)的子圖。
大多數(shù)現(xiàn)有的圖查詢(xún)系統(tǒng)(1、6、8、11、12、17、19、29、34、37-39、46]和算法[2-4、14、16、18、31、33、47]處理子圖匹配查詢(xún)的經(jīng)典Ullmann [40]回溯方法。我們?cè)诒疚闹兄攸c(diǎn)關(guān)注基于回溯的解決方案。在回溯過(guò)程中，查詢(xún)頂點(diǎn)（即查詢(xún)中的頂點(diǎn)）將按照匹配的順序映射到數(shù)據(jù)頂點(diǎn)（即數(shù)據(jù)圖中的頂點(diǎn)）?；厮葸^(guò)程可以看作是一個(gè)深度優(yōu)先搜索（DFS）樹(shù)，其中來(lái)自根的任何簡(jiǎn)單路徑都對(duì)應(yīng)于查詢(xún)的部分/完全匹配。例如，圖1顯示了用于在數(shù)據(jù)圖??中匹配查詢(xún)??的DFS樹(shù)，其中匹配的順序是??1???2???3???4???5。DFS樹(shù)中最左邊的路徑將查詢(xún)頂點(diǎn)（??1，??2，??3，??4，??5）映射到數(shù)據(jù)頂點(diǎn)（??0，??3，??2，??9，??6），，它對(duì)應(yīng)于??中??的完全匹配，即由{??0，??3，??2，??9，??6}誘導(dǎo)的??的子圖是??的匹配。第二條路徑將（??1，??2，??3，??4）映射到（??0，??3，??2，??10），，它對(duì)應(yīng)于??的部分匹配，但不能進(jìn)一步擴(kuò)展到匹配??5（因?yàn)??10映射到??4，??5是??4，??10的鄰居，必須在??中有一個(gè)標(biāo)記為‘E’的鄰居才能匹配??5）。

現(xiàn)有的解決方案和限制。雖然圖挖掘系統(tǒng)[7,11,17,24,38,42,44]和圖數(shù)據(jù)庫(kù)[6,10,19,29,37]可以用于處理子圖匹配查詢(xún)，但專(zhuān)門(mén)的子圖匹配系統(tǒng)[1,8,12,23,34,46]和算法[2-4,14-16,18,20,30,47]已經(jīng)被提出以提供更好的性能（第6節(jié)）。這些專(zhuān)門(mén)的解決方案使用了各種技術(shù)來(lái)減少冗余計(jì)算，包括消除由圖自同構(gòu)[1,8,11,12,17,34,38,39,46]引起的重復(fù)匹配，具有等價(jià)關(guān)系[15,20,30,34]的查詢(xún)頂點(diǎn)之間的計(jì)算共享，候選剪枝[2,3,14,16,18,20,47]，以及匹配順序選擇來(lái)減少回溯搜索空間[3,14,18,33,34]。
雖然現(xiàn)有的解決方案有效地減少了大量冗余計(jì)算，但在子圖匹配中存在一種關(guān)鍵的重復(fù)計(jì)算在很大程度上被忽略了。1當(dāng)我們?cè)诨厮輼?shù)的同一級(jí)別上擴(kuò)展部分匹配時(shí)，就會(huì)出現(xiàn)這種重復(fù)的計(jì)算。例如，在圖1c中，有三條路徑映射到??3到??2，??4映射到??9。為了擴(kuò)展這三條路徑以匹配??5，它是??3和??4的共同鄰居，現(xiàn)有的解決方案與這三條路徑的??2和??9的鄰居集相交。因此，同一鄰居集的交集操作被重復(fù)三次。這種冗余計(jì)算在圖的密集簇和冪律圖中非常常見(jiàn)。
雖然現(xiàn)有的解決方案有效地減少了大量冗余計(jì)算，但在子圖匹配中存在一種關(guān)鍵的重復(fù)計(jì)算在很大程度上被忽略了。1當(dāng)我們?cè)诨厮輼?shù)的同一級(jí)別上擴(kuò)展部分匹配時(shí)，就會(huì)出現(xiàn)這種重復(fù)的計(jì)算。例如，在圖1c中，有三條路徑映射到??3到??2，??4映射到??9。為了擴(kuò)展這三條路徑以匹配??5，它是??3和??4的共同鄰居，現(xiàn)有的解決方案與這三條路徑的??2和??9的鄰居集相交。因此，同一鄰居集的交集操作被重復(fù)三次。這種冗余計(jì)算在圖的密集簇和冪律圖中非常常見(jiàn)。
我們可以使用大規(guī)模的并行化來(lái)處理豐富的集合交集，以減少查詢(xún)延遲，例如，使用gpu[8,12,13]。然而，一種較弱的方法是通過(guò)有效地共享重復(fù)集合的交集。不幸的是，在回溯樹(shù)中的不同路徑之間啟用這種計(jì)算共享并不容易，因?yàn)橹貜?fù)的交集可能不屬于共享相同前綴的路徑（如圖1c所示），而且這些路徑可能不會(huì)被執(zhí)行連續(xù)地當(dāng)并行化發(fā)生時(shí)，計(jì)算共享變得更加困難，因?yàn)椴煌穆窂娇赡芄蚕硐嗤募辖患⑶疫@些路徑可能在不同的時(shí)間由不同的線程處理。非連續(xù)出現(xiàn)和并行化的問(wèn)題也使交叉結(jié)果的緩存無(wú)效。我們也可以使用BFS方法來(lái)消除這種冗余，通過(guò)分組共享相同交集和處于搜索樹(shù)的同一級(jí)別的部分匹配，但是BFS的內(nèi)存開(kāi)銷(xiāo)通常是禁止的[7,8,38,42]。因此，需要一種新的機(jī)制來(lái)實(shí)現(xiàn)部分匹配之間的計(jì)算共享，同時(shí)保持基于dfs的內(nèi)存效率。
在本文中，我們提出了一種新的基于壓縮的回溯方法，它可以生成壓縮的部分匹配組，以便計(jì)算可以在每個(gè)組內(nèi)共享。我們還設(shè)計(jì)了一個(gè)優(yōu)化策略來(lái)選擇壓縮方案，給予最低的估計(jì)計(jì)算冗余。為了將我們的基于壓縮的回溯方法應(yīng)用于現(xiàn)有的解決方案（例如，CFL [3]和GQL [16]）來(lái)提高它們的性能，我們提出了一個(gè)通用的子圖匹配框架，稱(chēng)為Circinus，它包括一個(gè)模塊化的優(yōu)化工作流和一個(gè)基于操作員的執(zhí)行管道。我們將基于壓縮的回溯方法作為Circinus中的一個(gè)模塊來(lái)實(shí)現(xiàn)，并提出了特定于壓縮的優(yōu)化，以加快查詢(xún)執(zhí)行。大量的實(shí)驗(yàn)結(jié)果表明，在現(xiàn)有的優(yōu)化技術(shù)的基礎(chǔ)上，進(jìn)一步大大減少了重復(fù)計(jì)算。與現(xiàn)有方法[3,13,16,17,28,34,36,41]相比，減少的計(jì)算性能有效地提高了幾個(gè)數(shù)量級(jí)。

2 MOTIVATION

盡管以往曾努力減少冗余計(jì)算，但在子圖匹配的回溯過(guò)程中仍存在著冗余計(jì)算的內(nèi)在來(lái)源。
觀察。考慮回溯樹(shù)中的第??級(jí)。對(duì)于第??級(jí)的每個(gè)節(jié)點(diǎn)??，根到??路徑匹配根據(jù)給定匹配順序匹配??第一個(gè)查詢(xún)頂點(diǎn)的部分匹配。設(shè)????+1為（??+1）個(gè)查詢(xún)頂點(diǎn)，如果????是????+1的鄰居并且在????+1之前排序，則????為????+1的父查詢(xún)頂點(diǎn)。在部分匹配中，映射到????的數(shù)據(jù)頂點(diǎn)????被稱(chēng)為????+1的父數(shù)據(jù)頂點(diǎn)。設(shè)????+1的父數(shù)據(jù)頂點(diǎn)集為P??+1。為了在第??級(jí)擴(kuò)展每個(gè)部分匹配以匹配????+1，我們執(zhí)行一個(gè)Exthend操作，計(jì)算N個(gè)??∈P??+1?????????????????（??），即????+1的所有父數(shù)據(jù)頂點(diǎn)的鄰居集的交集。例如，在圖1中，如果是????+1=??5，則它的父查詢(xún)頂點(diǎn)????為??3和??4。在圖1c中，（??0，??3，??2，??9）對(duì)應(yīng)于（??1，??2，??3，??4）的部分匹配，因此??2和??9是??5的父數(shù)據(jù)頂點(diǎn)。為了擴(kuò)展（??0，??3，??2，??9）來(lái)匹配??5，我們與??2的鄰域集相交和??9找到他們的共同鄰居有相同的標(biāo)簽，這給出了??6，因此擴(kuò)展匹配（??0，??3，??2，??9，??6）。
我們可以觀察到，交集只涉及父數(shù)據(jù)頂點(diǎn)的鄰居集，而映射到其他查詢(xún)頂點(diǎn)的數(shù)據(jù)頂點(diǎn)則是無(wú)關(guān)的。這提供了一個(gè)計(jì)算共享機(jī)會(huì)：如果每個(gè)級(jí)別上的部分匹配由父數(shù)據(jù)頂點(diǎn)分組，那么它們可以在執(zhí)行“擴(kuò)展”操作時(shí)共享交集結(jié)果。以圖1c為例，擴(kuò)展（??0，??3，??2，??9）、（??0，??4，??2，??9）和（??1，??8，??2，??9）匹配??5，我們可以將它們按（??2，??9）分組，與??2和??9的相鄰集相交一次，得到??6（匹配??5）。
驗(yàn)證。我們報(bào)告了兩種重要的子圖匹配方法，CFL [3]和GQL [16]，以及最近的一個(gè)系統(tǒng)游隼[17]的計(jì)算冗余。我們測(cè)量了每種方法中集合交集計(jì)算的數(shù)量。作為參考，我們還計(jì)算了每種方法的集合交集調(diào)用的最優(yōu)數(shù)量，這些方法是通過(guò)在回溯樹(shù)的同一級(jí)別上的所有部分匹配之間共享計(jì)算來(lái)實(shí)現(xiàn)的。我們將對(duì)實(shí)驗(yàn)設(shè)置的完整描述推遲到第5.3節(jié)。我們發(fā)現(xiàn)，對(duì)于所有的三個(gè)解，實(shí)際的交點(diǎn)計(jì)數(shù)和相應(yīng)的最優(yōu)數(shù)之間的差值可以是一到兩個(gè)數(shù)量級(jí)。即重復(fù)計(jì)算占總集合交集計(jì)算的90%-99%，為計(jì)算共享提供了很大的空間。

3 COMPRESSION-BASED BACKTRACKING

我們提出了一種新的基于壓縮的回溯方法，該方法通過(guò)在回溯搜索樹(shù)的每個(gè)級(jí)別上對(duì)部分匹配進(jìn)行分組來(lái)實(shí)現(xiàn)計(jì)算共享，同時(shí)仍然遵循DFS方法來(lái)有效地使用內(nèi)存。

3.1 Subgraph Compression

我們首先用一個(gè)例子來(lái)說(shuō)明其主要思想。考慮圖1中所示的查詢(xún)??和匹配的順序??1???2???3???4???5。對(duì)于1≤??≤5，設(shè)????為由{??1，??2，……，????}誘導(dǎo)的??的子圖，如圖2所示，設(shè)????為圖1中DFS樹(shù)的??級(jí)的部分匹配集，即????的匹配。例如，??4由{??0，??3，??2，??9}，{??0，??3，??2，??10}，{??0，??4，??2，??9}，和{??1，??8，??2，??9}，誘導(dǎo)的??的四個(gè)子圖組成，它們都與??4相匹配（如圖2所示）。

我們的目標(biāo)是在將????擴(kuò)展到????+1時(shí)（按鍵）分組每個(gè)????中的子圖（即匹配??中的????+1），以最大化計(jì)算共享。考慮將??4擴(kuò)展到??5，最優(yōu)分組將是使用{??3，??4}（即{??2，??9}，{??2，??10}）的映射作為鍵，它允許??2和??9的鄰居集的交集在??4中的三個(gè)部分匹配之間共享。然而，這種最優(yōu)分組需要完全計(jì)算????，這本質(zhì)上是一種BFS方法，而且內(nèi)存禁止。
我們能否為每個(gè)級(jí)別一次計(jì)算一個(gè)組，而不是像BFS方法那樣計(jì)算所有組，同時(shí)仍然有效地共享計(jì)算？受CBF2 [28]中壓縮技術(shù)的啟發(fā)，我們建議使用????的頂點(diǎn)覆蓋（VC）來(lái)設(shè)置分組鍵。對(duì)于每個(gè)????，映射到頂點(diǎn)覆蓋物中的查詢(xún)頂點(diǎn)的數(shù)據(jù)頂點(diǎn)被設(shè)置為分組鍵。
考慮到??4，并使用{??1，??3，??4}作為其VC。在??4中的部分匹配中映射到（??1、??3，??4）的數(shù)據(jù)頂點(diǎn)為（??0、??2、??9）、（??0、??2、??10）、（??0、??2、??9）、（??1，??2，??9）。因此，如果我們使用映射數(shù)據(jù)頂點(diǎn)作為鍵，??4被分為三組：（??0，{??3，??4}，??2，??9），（??0，{??3}，??2，??10），（??1，{??8}，??2，??9），其中（??0，??3，??2，??9）和（??0，??4，??2，??9）被壓縮成一個(gè)組（??0，{??3，??4}，??2，??9），可以通過(guò)共享??2和??9的鄰居的交集來(lái)進(jìn)行擴(kuò)展。請(qǐng)注意，在這個(gè)示例中，壓縮（以及計(jì)算共享）在這個(gè)玩具示例中并不令人印象深刻，但在如圖11所示的真實(shí)數(shù)據(jù)圖中非常重要，我們將在第5.3節(jié)中展示更多內(nèi)容。

3.2 Compression-based Extend Operator

利用基于vc的分組，我們?cè)O(shè)計(jì)了一個(gè)新的Extend算子，它計(jì)算壓縮組上的擴(kuò)展，并將標(biāo)準(zhǔn)的回溯過(guò)程轉(zhuǎn)換為基于壓縮的回溯。
設(shè)計(jì)選擇。在我們對(duì)Extend操作符的設(shè)計(jì)中，我們做了以下三個(gè)設(shè)計(jì)選擇來(lái)綁定內(nèi)存使用，并確保低分組開(kāi)銷(xiāo)。
首先，我們強(qiáng)制執(zhí)行每個(gè)分組鍵必須是組中子圖的VC，這樣Extend就可以在每個(gè)級(jí)別上一次生成一組部分匹配，而不像基于BFS的方法那樣存儲(chǔ)整個(gè)級(jí)別的部分匹配。對(duì)于每一組部分匹配，基于vc的壓縮[28]避免了枚舉組中集合的交叉積，即，對(duì)于沒(méi)有壓縮的組（??1，{??1，…，????}，??2，{??1，…，????}），，我們需要以（??1，????，??2，????）.的形式枚舉??（????）部分匹配因此，基于vc的壓縮減少了內(nèi)存開(kāi)銷(xiāo)。特別是，在回溯的每一步中，壓縮組所需的內(nèi)存受到非vc查詢(xún)頂點(diǎn)的映射數(shù)據(jù)頂點(diǎn)總數(shù)加上一個(gè)小常量的限制。因此，實(shí)際中內(nèi)存使用很小（第5.2.3節(jié)）。
其次，我們要求????的頂點(diǎn)覆蓋????包含在????+1的頂點(diǎn)覆蓋????+1中，即?????????+1。這是因?yàn)楫?dāng)我們匹配????+1時(shí)，如果是?????????+1，則需要同時(shí)生成和處理許多????匹配組，以便將????+1的匹配組重新分組，這將導(dǎo)致很高的開(kāi)銷(xiāo)。
第三，Extend操作符直接以壓縮格式計(jì)算擴(kuò)展，并通過(guò)直接使用交集結(jié)果將非vc集維護(hù)在壓縮組中，以避免壓縮和解壓縮的額外計(jì)算。
擴(kuò)展算法。算法1給出了擴(kuò)展算子。給定子查詢(xún)????的部分匹配的壓縮組????，其中部分匹配基于????的頂點(diǎn)覆蓋????具有相同的分組鍵，Extend擴(kuò)展????以匹配（??+1）個(gè)查詢(xún)頂點(diǎn)??，如下所示。設(shè)??為??的父查詢(xún)頂點(diǎn)的集合，即那些與??相鄰但在??之前的查詢(xún)頂點(diǎn)，????+1為????+1所選擇的VC。有三種情況：
1 ???????+1；
2 ??∩????+1=?；
3 ??∩????+1=?和???????+1。
請(qǐng)注意，案例2和案例3的??∈????+1，否則，連接??和??中的父頂點(diǎn)的一些邊沒(méi)有被覆蓋。表示與父查詢(xún)頂點(diǎn)??匹配的??的鄰居集為A????（??），其中的鄰居是目標(biāo)查詢(xún)頂點(diǎn)??的候選對(duì)象。由于剪枝采用了各種過(guò)濾規(guī)則，如通過(guò)查詢(xún)頂點(diǎn)標(biāo)簽進(jìn)行過(guò)濾，避免同一部分匹配中的重復(fù)頂點(diǎn)，因此匹配不同??的??鄰居可能會(huì)不同。
在案例1（行1-5），映射集????（即，用于映射到??的數(shù)據(jù)頂點(diǎn)）計(jì)算通過(guò)調(diào)用擴(kuò)展計(jì)算的鄰居集的交集數(shù)據(jù)頂點(diǎn)????映射到??查詢(xún)頂點(diǎn)。具體來(lái)說(shuō)，在第16行中，get鄰域交集（??，????????，????）計(jì)算N??∈????????A????（????.getKey（??））。如果??在頂點(diǎn)覆蓋????+1中，則對(duì)于每個(gè)頂點(diǎn)??∈??，調(diào)用addKey將??添加到????中以生成新的組????+1，并將??添加到????+1的分組鍵中。否則，調(diào)用addSet將??添加到????以生成一個(gè)新的組????+1。圖2顯示了一個(gè)示例，其中黑色頂點(diǎn)是每個(gè)子查詢(xún)????的VC?？紤]將??1擴(kuò)展到??2，我們有??=??2和??={??1}和????+1=??2={??1}，，從?????2.開(kāi)始，它是Case 1有兩個(gè)壓縮組匹配（??1）：（??0）和（??1）。為了擴(kuò)展??1=（??0），我們首先從??0的鄰居集（所有屬于??0的鄰居集）中得到??的映射集標(biāo)簽不是‘B’被過(guò)濾掉了，參見(jiàn)圖1b中的??0的鄰居)，這給出了??={??3，??4}。由于??2不在??2中，所以我們只需將??添加到??1中，以獲得??2=（??0，{??3，??4}），如圖2所示。在這里，??2是一個(gè)壓縮組，存儲(chǔ)兩個(gè)部分匹配項(xiàng)（??0，??3）和（??0，??4）。

在案例1中有一個(gè)特殊的場(chǎng)景，當(dāng)???????+1，但是???????，即，一些映射到????中的集合的父查詢(xún)頂點(diǎn)被添加到????+1的VC中。在這種情況下，我們需要部分解壓????，并通過(guò)枚舉這些映射集的乘積來(lái)生成多個(gè)組。然后我們對(duì)每個(gè)生成的組調(diào)用擴(kuò)展。
在情況2（第6-10行）中，我們首先選擇一個(gè)具有最小映射集????????的父查詢(xún)頂點(diǎn)????????。然后，我們計(jì)算一個(gè)??的候選集??作為????????中所有頂點(diǎn)的鄰域集的并集，即??←D??∈????????A??????????（??）。對(duì)于每個(gè)候選的??∈??，??是一個(gè)數(shù)據(jù)頂點(diǎn)，如果??是??的所有父數(shù)據(jù)頂點(diǎn)的鄰居，則可以用于映射到??。因此，對(duì)于每個(gè)??∈??，我們調(diào)用擴(kuò)展fromSet來(lái)計(jì)算??的鄰居集和每個(gè)??∈??的映射集之間的交集。如果交叉點(diǎn)（對(duì)于所有的??∈??）不是空的，則找到??的映射數(shù)據(jù)頂點(diǎn)??并生成一個(gè)新的組，并將??添加到分組鍵中（因?yàn)??在VC中）。為了說(shuō)明這一點(diǎn)，考慮在圖2中將??3擴(kuò)展到??4，我們有??=??4，??={??2}和??4={??1，??3，??4}，，這是??N??4=?.以來(lái)的Case 2考慮擴(kuò)展??3的壓縮組（??0，{??3，??4}，??2），我們有????????=??2 and????????={??3，??4}。我們通過(guò)??3和??4的鄰居集的并集來(lái)計(jì)算??={??9，??10}（所有標(biāo)簽不是D的鄰居都被過(guò)濾掉）。然后我們將擴(kuò)展集調(diào)用為將??9的鄰域集與??2的映射集相交，它給出了{(lán)??3，??4}和一個(gè)新的??4的壓縮群（??0，{??3，??4}，??2，??9）。我們還將??10的鄰域集和??2的映射集相交，它給出了{(lán)??3}和另一組??4（??0，{??3}，??2，??10）。
在案例3（第11-14行）中，我們將??分為兩個(gè)集合：????????是VC的一部分，而????????是??中剩余的頂點(diǎn)。我們使用????????計(jì)算案例1中的??的映射集，對(duì)于每個(gè)??∈??，使用案例2中的????????生成新的壓縮組。

3.3 Backtracking

算法2顯示了整個(gè)回溯過(guò)程。我們可以通過(guò)以給定的匹配順序初始化第一個(gè)查詢(xún)頂點(diǎn)??1的壓縮組(s)來(lái)開(kāi)始匹配一個(gè)查詢(xún)。如果在VC中選擇??1，則??1的每個(gè)映射數(shù)據(jù)頂點(diǎn)形成一個(gè)壓縮組（第4行）；否則，??1的映射數(shù)據(jù)頂點(diǎn)集形成一個(gè)壓縮組（第5行）。然后，該算法遞歸地?cái)U(kuò)展每個(gè)壓縮組，通過(guò)DFS找到??的匹配，使用Extend作為生成器。

3.4 Selection of Vextex Covers

我們首先分析了基于壓縮的回溯如何減少冗余計(jì)算，然后引入了一種為每個(gè)子查詢(xún)選擇VC的策略。
讓我們來(lái)考慮一下???????吧。在這種情況下，包含??的相同父數(shù)據(jù)頂點(diǎn)的所有????匹配項(xiàng)都必須在同一個(gè)壓縮組中，因此它們可以共享集合的交集結(jié)果。因此，將????的匹配擴(kuò)展到????+1的匹配，而可以通過(guò)任何更好的分組保存的匹配，沒(méi)有冗余?，F(xiàn)在考慮???????，包含??的相同父數(shù)據(jù)頂點(diǎn)的????匹配，由于分組鍵中的非父數(shù)據(jù)頂點(diǎn)的不同，即映射到??∈????\（????∩??）的數(shù)據(jù)頂點(diǎn)。因此，對(duì)于較少的計(jì)算冗余，首選一個(gè)導(dǎo)致較少這樣的分組密鑰的VC。
成本模型。我們?cè)O(shè)計(jì)了一個(gè)成本模型來(lái)估計(jì)擴(kuò)展????到????+1所需的計(jì)算成本：

其中，????????????（??）是為擴(kuò)展????而處理的壓縮組的（估計(jì)的）數(shù)量，這些壓縮組是基于一個(gè)頂點(diǎn)覆蓋??生成的。方程中的第一項(xiàng)對(duì)應(yīng)于所有擴(kuò)展鍵調(diào)用的估計(jì)交點(diǎn)總數(shù)，其中|????????|是一個(gè)擴(kuò)展鍵調(diào)用中的交點(diǎn)數(shù)。第二項(xiàng)對(duì)應(yīng)于估計(jì)的交叉口總數(shù)擴(kuò)展調(diào)用，其中|????????|十字路口的數(shù)量在一個(gè)擴(kuò)展調(diào)用，和????????????+1（??∪{??}）估計(jì)的所有??的總大小在案例2或3所有????????（即，調(diào)用時(shí)????????=?）.請(qǐng)注意，????????????（??）≤????????????（??∪{??}），因?yàn)閷??添加到分組鍵中，因此只會(huì)創(chuàng)建更精細(xì)的組。因此，與??重疊更小的頂點(diǎn)覆蓋??可能得到更小的??????????（??）。
為了估計(jì)????????????（??），我們使用??中每個(gè)查詢(xún)頂點(diǎn)的候選點(diǎn)（即可能匹配）基數(shù)的乘積（例如，使用基于查詢(xún)頂點(diǎn)的標(biāo)簽和度的數(shù)據(jù)圖中的標(biāo)簽頻率或度分布）。或者，當(dāng)生成查詢(xún)頂點(diǎn)的匹配集時(shí)，我們可以計(jì)算????????????（??）作為[3,14]中路徑權(quán)值計(jì)算后可能的回溯搜索空間，以進(jìn)行更緊密的估計(jì)。
搜索策略。算法3展示了如何生成風(fēng)投。讓??1，??2，……，????是由匹配順序定義的子查詢(xún)序列，其中??是給定查詢(xún)??中的頂點(diǎn)數(shù)。即使在包含約束?????????+1下（在上面的“設(shè)計(jì)選擇”中討論過(guò)），為每個(gè)????找到最佳VC的搜索空間也很大。
我們沒(méi)有搜索整個(gè)空間，即??（2??（??+1）/2）大小的??級(jí)別組合，每個(gè)級(jí)別??有2個(gè)??枚舉，而是生成一個(gè)相對(duì)較小的搜索空間U，大小為??（??2），如第1-10行所示。我們首先通過(guò)分支和綁定（第3行）為每個(gè)子查詢(xún)????生成一個(gè)最小權(quán)重的頂點(diǎn)覆蓋??????，使用????????????（{??}）作為????中每個(gè)查詢(xún)頂點(diǎn)??的權(quán)重。接下來(lái)，對(duì)于每個(gè)??，我們?yōu)槊總€(gè)????計(jì)算一個(gè)最小權(quán)重頂點(diǎn)覆蓋??????，其中1≤??≤??和??=??，同時(shí)強(qiáng)制執(zhí)行包含約束?????????????+1。具體來(lái)說(shuō)，我們使用一個(gè)賦值表來(lái)根據(jù)??????預(yù)先分配頂點(diǎn)，并在具有空賦值的頂點(diǎn)上運(yùn)行分支和綁定。
然后，我們使用動(dòng)態(tài)規(guī)劃（DP）來(lái)尋找最小化總成本????=I???1??=1??????????（????）來(lái)匹配??=????（行11-18）。我們定義了一個(gè)DP表??，其中??（??，??????）記錄了當(dāng)選擇??????作為????的VC時(shí)，匹配????+1的最小總成本。我們?yōu)槊總€(gè)??1??初始化??（1，??1??）（注??1??={??1}或?）：

然后，我們遞歸地計(jì)算1個(gè)<??<??和??????∈U??的??（??，??????）。我們將??????1設(shè)置為??????的父項(xiàng)，用于DP表中的回溯跟蹤（第17行）。為了檢索vc的最佳序列，我們選擇了最小化????=??（???1，?????1）的頂點(diǎn)覆蓋?????1∈?????1，并遞歸追溯。對(duì)于??的VC，我們采用最小權(quán)重頂點(diǎn)覆蓋??????????1（Line19行）。DP的時(shí)間復(fù)雜度為??（??2·??），其中??（??=Ω，??）為計(jì)算????????????（??）的復(fù)雜度。

3.5 Discussion

我們?nèi)绾闻cBFS/DFS方法進(jìn)行比較？我們的方法在壓縮組的粒度上進(jìn)行DFS。與現(xiàn)有的單獨(dú)處理部分匹配的BFS和DFS方法相比，我們的方法可以歸類(lèi)為一種BFS/DFS混合方法，但與所有現(xiàn)有的混合方法具有不同的目標(biāo)和技術(shù)解決方案?，F(xiàn)有的結(jié)合BFS和DFS [7,12,39,44,46]的工作旨在平衡內(nèi)存使用和并行化效率。他們使用BFS來(lái)增加并行性，而不是減少重復(fù)的計(jì)算。事實(shí)上，基于BFS的方法被廣泛用于基于gpu的解決方案[8,12,13]或分布式解決方案[7,38,44]利用大規(guī)模并行性并提供良好的負(fù)載平衡（第6節(jié)）。從技術(shù)角度來(lái)看，現(xiàn)有的混合方法要么采用基于批處理的方法（例如，以DFS方式處理批，但在每個(gè)批處理BFS）[7,12,44]，要么根據(jù)生成的部分匹配的數(shù)量在BFS和DFS [39,46]之間動(dòng)態(tài)切換。批處理或切換要么基于預(yù)設(shè)的閾值或運(yùn)行時(shí)內(nèi)存可用性，這與查詢(xún)無(wú)關(guān)。例如，PBE-repess[13]將可用的內(nèi)存分配給回溯樹(shù)的每個(gè)級(jí)別以存儲(chǔ)中間結(jié)果，并在當(dāng)前級(jí)別的緩沖區(qū)滿(mǎn)時(shí)從BFS切換到DFS。相比之下，我們的解決方案利用了查詢(xún)模式來(lái)最大化計(jì)算共享。BFS實(shí)際上發(fā)生在壓縮組中（這里，“虛擬”表示組中的部分匹配沒(méi)有真正枚舉），而組則以DFS方式計(jì)算。此外，我們的方法可以應(yīng)用于單線程解決方案（例如，CFL、GQL），以提高其性能（第5.2.1節(jié)），而現(xiàn)有的混合方法僅適用于并行場(chǎng)景。

我們?nèi)绾闻c最壞情況下的最優(yōu)連接進(jìn)行比較？同構(gòu)子圖匹配是npp完整的[9]。這個(gè)問(wèn)題可以表示為數(shù)據(jù)庫(kù)研究中的一個(gè)連接問(wèn)題，其中每個(gè)查詢(xún)邊表示一個(gè)關(guān)系，每個(gè)查詢(xún)頂點(diǎn)表示一個(gè)屬性。最壞情況下的最優(yōu)連接（WCOJ）保證了運(yùn)行時(shí)間與最壞情況下的輸出大小成正比，這在理論上優(yōu)于二進(jìn)制連接。我們將討論我們的方法與WCOJ之間的關(guān)系。
Ngo等人[26]提出了一種通用的WCOJ算法，該算法推廣了包括WCOJ TrieJoin [41]在內(nèi)的重要算法。在子圖匹配的上下文中，WCOJ在單個(gè)多路連接中處理與查詢(xún)頂點(diǎn)??相關(guān)聯(lián)的所有關(guān)系，其時(shí)間復(fù)雜度與最小的關(guān)系大小成正比。WCOJ使用回溯并處理“一次查詢(xún)頂點(diǎn)”，Circinus也是如此，而二進(jìn)制連接則處理“一次查詢(xún)邊”。Circinus是通用WCOJ算法[26]的一個(gè)實(shí)例化（具有共享計(jì)算），當(dāng)頂點(diǎn)覆蓋只啟用算法1中的情況1時(shí)。具體來(lái)說(shuō)，通用的WCOJ算法允許對(duì)查詢(xún)頂點(diǎn)集進(jìn)行任意分區(qū)以進(jìn)行遞歸查詢(xún)分解，并且只有情況1的循環(huán)算法將（子）查詢(xún)????由{??1、···、?????1}和{????}進(jìn)行分區(qū)。擴(kuò)展fromkey本質(zhì)上是一個(gè)多路排序合并連接，其運(yùn)行時(shí)間與最小的鄰居集大小3成比例。對(duì)于情況2和情況3，不能保證候選集??的計(jì)算的運(yùn)行時(shí)間與最小關(guān)系（即最小父鄰居集）的大小成正比。然而，Circinus使用成本模型（參考第3.4節(jié)）進(jìn)行計(jì)劃優(yōu)化，當(dāng)它比只有案例1的替代方案便宜時(shí)，只允許案例2和案例3。我們?cè)诘?.2節(jié)中與跳蛙三化join進(jìn)行了比較。
現(xiàn)有的解決方案可以輕松地?cái)U(kuò)展到基于壓縮的回溯嗎？我們的基于壓縮的方法是為基于回溯的解決方案而設(shè)計(jì)的，并與許多優(yōu)化匹配順序、候選過(guò)濾或數(shù)據(jù)圖布局的現(xiàn)有技術(shù)相正交。我們?cè)诘?.2節(jié)中證明，我們的方法可以應(yīng)用于現(xiàn)有的算法（即CFL和GQL），并進(jìn)一步顯著提高了它們的性能。但是，從實(shí)現(xiàn)的角度來(lái)看，現(xiàn)有的子圖匹配解決方案不能輕易地?cái)U(kuò)展到支持基于壓縮的回溯，原因如下。在現(xiàn)有的解決方案中，子圖匹配的邏輯是在一個(gè)嵌套的for循環(huán)中編寫(xiě)的，并且優(yōu)化邏輯（如自同構(gòu)消除和候選過(guò)濾）和查詢(xún)?cè)u(píng)估邏輯（如集合交集和枚舉）都與存儲(chǔ)部分匹配的數(shù)據(jù)結(jié)構(gòu)緊密集成。然而，基于壓縮的回溯使用壓縮組來(lái)表示部分匹配，這需要我們更改數(shù)據(jù)結(jié)構(gòu)，以在現(xiàn)有解決方案中存儲(chǔ)部分匹配，而這本身就需要修改現(xiàn)有解決方案中的大部分代碼庫(kù)。這促使我們建立一個(gè)總體框架。我們提供了一個(gè)帶有抽象回溯邏輯的“擴(kuò)展”操作符的模塊化設(shè)計(jì)，一個(gè)用于生成帶有附加過(guò)濾器和檢查的操作符鏈的優(yōu)化器，以及一個(gè)基于推送的執(zhí)行模型。通過(guò)這種設(shè)計(jì)，基于壓縮的優(yōu)化和其他技術(shù)可以很容易地結(jié)合起來(lái)，以處理需要不同技術(shù)的不同類(lèi)型的查詢(xún)和圖（例如，已標(biāo)記的、未標(biāo)記的）。

4 QUERY EXECUTION

為了應(yīng)用基于壓縮的回溯算法，我們提出了一個(gè)子圖匹配框架，稱(chēng)為Circinus，以及一些查詢(xún)執(zhí)行的優(yōu)化。

4.1 The Circinus Framework

為了使我們的方法作為一種通用的優(yōu)化，可以應(yīng)用于現(xiàn)有的解決方案，以提高其性能，我們將Circinus設(shè)計(jì)為一個(gè)通用的優(yōu)化和執(zhí)行框架。該框架是一個(gè)模塊化設(shè)計(jì)，因此可以很容易地插入用來(lái)優(yōu)化子圖匹配的每一步的各種技術(shù)。圖3顯示了該框架的概述，它包括七個(gè)模塊及其之間的流動(dòng)。在右邊，我們還列出了在每個(gè)模塊中使用的代表性技術(shù)的摘要。

模塊1到4是用于基于回溯的子圖匹配的通用，這些模塊中的一些優(yōu)化技術(shù)在現(xiàn)有的解決方案中常用。模塊1～3形成查詢(xún)規(guī)劃邏輯，首先在沒(méi)有數(shù)據(jù)圖或執(zhí)行層知識(shí)的情況下分析查詢(xún)圖，然后使用分析結(jié)果生成邏輯計(jì)劃，最后基于邏輯計(jì)劃和來(lái)自執(zhí)行層的信息構(gòu)造物理計(jì)劃。然后，模塊4通過(guò)回溯來(lái)執(zhí)行物理計(jì)劃，并可能使用并行化來(lái)進(jìn)行密集的計(jì)算。
模塊5和模塊6支持專(zhuān)門(mén)的優(yōu)化，如各種修剪規(guī)則（例如，數(shù)據(jù)頂點(diǎn)標(biāo)簽、度、鄰域標(biāo)簽頻率、候選集中是否存在鄰居等）。為每個(gè)查詢(xún)頂點(diǎn)修剪候選匹配項(xiàng)。輔助數(shù)據(jù)結(jié)構(gòu)也可以使用改進(jìn)的候選數(shù)據(jù)集來(lái)構(gòu)建，以促進(jìn)回溯。特定于查詢(xún)的成本（例如，子圖計(jì)數(shù)的估計(jì)和擴(kuò)展成本）是從輔助數(shù)據(jù)結(jié)構(gòu)或數(shù)據(jù)圖中計(jì)算出來(lái)的，可用于計(jì)算替代匹配順序的成本。模塊7生成一個(gè)基于壓縮的計(jì)算共享查詢(xún)計(jì)劃（第3節(jié)）。
圖3顯示了Circinus中的一般工作流程，包括兩個(gè)計(jì)劃階段和兩個(gè)執(zhí)行階段。第一個(gè)規(guī)劃階段包括模塊1和模塊5，然后是第一個(gè)執(zhí)行階段的模塊6。如果不需要在模塊5中生成候選集，則會(huì)跳過(guò)模塊6中的執(zhí)行。第二個(gè)規(guī)劃階段由模塊2、模塊7和模塊3組成，然后由模塊4最終執(zhí)行。

4.2 Compression Specific Optimizations

Circinus支持幾種特定于基于壓縮的回溯的優(yōu)化。對(duì)壓縮組的戰(zhàn)略性修剪。在回溯過(guò)程中，只有當(dāng)我們輸出匹配的子圖時(shí)，一個(gè)被壓縮的組才會(huì)被完全解壓縮。但是，由于將相同的數(shù)據(jù)頂點(diǎn)匹配到多個(gè)查詢(xún)頂點(diǎn)，可以找到一些壓縮組沒(méi)有有效匹配。這是有兩個(gè)原因。首先，當(dāng)同一壓縮組中的多個(gè)映射集匹配相同標(biāo)簽的查詢(xún)頂點(diǎn)時(shí)，它們可能包含重疊的數(shù)據(jù)頂點(diǎn)。具體來(lái)說(shuō)，如果有??個(gè)這樣的映射集，但它們共同包含少于??個(gè)的不同頂點(diǎn)，整個(gè)壓縮組都無(wú)效，應(yīng)盡早進(jìn)行修剪。其次，當(dāng)一個(gè)頂點(diǎn)作為鍵添加到壓縮組時(shí)，它可能會(huì)出現(xiàn)在一些現(xiàn)有的映射集中。
我們?cè)O(shè)計(jì)了一個(gè)修剪策略，在每個(gè)壓縮組生成時(shí)適用于它，以避免對(duì)無(wú)效組的無(wú)用計(jì)算?？紤]一個(gè)與????匹配的壓縮組，讓????的標(biāo)簽為??。我們?cè)O(shè)置了一個(gè)剪枝閾值????，它是在????中帶有標(biāo)簽??的查詢(xún)頂點(diǎn)的數(shù)量。我們提取所有標(biāo)簽為??和大小小于????的映射集。然后，我們檢查在它們的笛卡爾乘積中是否至少有一個(gè)元組沒(méi)有重復(fù)，也不與標(biāo)簽??的鍵重疊。如果沒(méi)有找到元組，我們將修剪壓縮的組。
注意，對(duì)于有效的壓縮組，不同的映射集中可能存在重疊頂點(diǎn)，但這不會(huì)導(dǎo)致無(wú)用的計(jì)算，因?yàn)椋?(1)在擴(kuò)展fromkey的情況下，映射集不參與計(jì)算，并且有效和無(wú)效部分匹配的計(jì)算在組中共享；(2)在擴(kuò)展的情況下，通過(guò)相交父查詢(xún)頂點(diǎn)與目標(biāo)數(shù)據(jù)頂點(diǎn)的鄰居頂點(diǎn)關(guān)聯(lián)的映射集獨(dú)立更新。
支持使用輔助數(shù)據(jù)結(jié)構(gòu)的算法。GQL [16]和CFL [3]等算法為每個(gè)查詢(xún)頂點(diǎn)計(jì)算一個(gè)候選頂點(diǎn)集，并建立輔助的二部圖來(lái)處理每個(gè)給定的查詢(xún)。構(gòu)建二部圖的空間復(fù)雜度較高，即??（|????|×|????|），其中|????|為數(shù)據(jù)圖??中的邊數(shù)，|????|為查詢(xún)??中的邊數(shù)。因此，為了獲得更好的可伸縮性，我們避免構(gòu)造二部圖，而是在擴(kuò)展fromkey中添加目標(biāo)查詢(xún)頂點(diǎn)的候選集，并動(dòng)態(tài)計(jì)算候選邊。請(qǐng)注意，由于Circinus已經(jīng)避免了重復(fù)計(jì)算，因此它從使用二部圖（用空間交換時(shí)間）中獲益不多。
來(lái)自壓縮集的自適應(yīng)擴(kuò)展。在算法1的情況2中，通過(guò)并集計(jì)算一個(gè)目標(biāo)集??。當(dāng)使用GQL [16]和CFL [3]等算法，為目標(biāo)查詢(xún)頂點(diǎn)生成一個(gè)小的候選集，其大小小于估計(jì)的并集大小時(shí)，可以通過(guò)直接使用候選集作為??而不是計(jì)算并集來(lái)減少計(jì)算。??的計(jì)算在運(yùn)行時(shí)被調(diào)整，用于每個(gè)壓縮組的擴(kuò)展。

4.3 Parallelization and Load Balancing

為了支持高效的并行計(jì)算，Circinus使用分塊和最低級(jí)任務(wù)分割策略進(jìn)行負(fù)載平衡。
塊。在多線程執(zhí)行的情況下，Circinus將初始的部分匹配劃分為塊。分配一個(gè)任務(wù)來(lái)在一個(gè)塊上運(yùn)行整個(gè)執(zhí)行管道。由于從每個(gè)初始部分匹配開(kāi)始的搜索空間可能不同，Circinus利用在查詢(xún)計(jì)劃階段計(jì)算的初始部分匹配的成本來(lái)生成負(fù)載平衡塊。如果所選的規(guī)劃策略不計(jì)算成本，則使用映射到第一個(gè)查詢(xún)頂點(diǎn)的數(shù)據(jù)頂點(diǎn)的程度。
最低級(jí)任務(wù)分割。由于用于生成塊的成本可能不準(zhǔn)確，Circinus在查詢(xún)執(zhí)行過(guò)程中動(dòng)態(tài)地維護(hù)負(fù)載平衡。如果未完成任務(wù)的數(shù)量小于可用線程，則向正在運(yùn)行的任務(wù)發(fā)送信號(hào)以進(jìn)行任務(wù)分割。當(dāng)接收到信號(hào)時(shí)，任務(wù)不是在DFS樹(shù)的當(dāng)前級(jí)別計(jì)算和分割一批輸出，而是首先在其輸入塊中分割部分匹配以創(chuàng)建新任務(wù)。當(dāng)在當(dāng)前最低級(jí)別沒(méi)有要拆分的部分匹配時(shí)（即，最接近DFS樹(shù)根的未完成級(jí)別）時(shí)，任務(wù)計(jì)算下一級(jí)別的部分匹配，并將它們拆分以創(chuàng)建新任務(wù)。因此，該任務(wù)總是在盡可能低的級(jí)別上進(jìn)行計(jì)算和分割。這個(gè)底層策略的原因是部分匹配在較低的期望有更多的計(jì)算，和分裂在底層首先使原始任務(wù)和新任務(wù)搜索子樹(shù)根在同一級(jí)別，這樣他們有類(lèi)似的負(fù)荷。

5 EXPERIMENTAL EVALUATION

我們?cè)诓煌臄?shù)據(jù)集和查詢(xún)?cè)O(shè)置上評(píng)估了Circinus，以回答以下三個(gè)問(wèn)題：
(1)Circinus與最先進(jìn)的解決方案相比如何？
(2)圓如何有效地減少冗余計(jì)算？
(3)Circinus中的各種設(shè)置（如????????????（??）、并行性）如何影響其性能？

5.1 Experimental Setup

數(shù)據(jù)集。我們使用了6個(gè)真實(shí)世界的數(shù)據(jù)集，這些數(shù)據(jù)集通常用于評(píng)估之前的子圖匹配方法[3,17,22,24,36]。表1列出了它們的統(tǒng)計(jì)數(shù)據(jù)。HM是一個(gè)帶有標(biāo)簽的生物網(wǎng)絡(luò)。YT2描述了從2007年2月到5月發(fā)布的Youtube視頻，每個(gè)視頻都用一個(gè)頂點(diǎn)表示，如果兩個(gè)視頻是相關(guān)的，就有一條邊，視頻類(lèi)別就是標(biāo)簽。其他數(shù)據(jù)集是未標(biāo)記的社交網(wǎng)絡(luò)，它的標(biāo)簽被隨機(jī)分配到之前的標(biāo)簽集的數(shù)據(jù)頂點(diǎn)。
查詢(xún)。我們使用了8個(gè)未標(biāo)記的查詢(xún)，如圖4所示，其中??1-??7也被用于評(píng)估游隼[17]，CBF [28]和PBE [12,13]（PBE使用了??1，??2和??5）。對(duì)于有標(biāo)記的查詢(xún)，我們通過(guò)隨機(jī)游走和BFS從每個(gè)數(shù)據(jù)集中提取子圖來(lái)生成查詢(xún)，遵循之前的工作[2,3,14,15,30,36]。我們生成了4組查詢(xún)，{??6，??8，??12，??16}，其中每個(gè)集合????由200個(gè)查詢(xún)組成，??∈{6,8,12,16}是每個(gè)查詢(xún)中的頂點(diǎn)數(shù)量。除非另有說(shuō)明，所有實(shí)驗(yàn)都是在兩個(gè)2.1 GHz Intel ? Xeon ?銀色4110 CPU的機(jī)器上運(yùn)行的，超線程（16核，32個(gè)超線程）和128GB RAM，運(yùn)行64位Debian9.8版本。

5.2 Performance Comparison

我們首先報(bào)告了Circinus (1)與游隼[17]、青蛙Trie（LFTJ）[41]，CFL[3]和GQL [16]對(duì)標(biāo)記查詢(xún)的比較結(jié)果，以及(2)與游隼、LFTJ、GraphPi[34]，PBE-重用[13]和CBF [28]對(duì)未標(biāo)記查詢(xún)的比較結(jié)果。CFL和GQL是兩種有效的標(biāo)記子圖匹配算法。游隼是一種最先進(jìn)的圖挖掘系統(tǒng)，它支持子圖匹配。LFTJ是商業(yè)數(shù)據(jù)庫(kù)LogicBlox中采用的一種開(kāi)創(chuàng)性的最壞情況最優(yōu)連接算法。PBE重用和CBF是專(zhuān)門(mén)的無(wú)標(biāo)記子圖匹配方法，其中PBE重用是一個(gè)多線程系統(tǒng)，CBF基于MapReduce。對(duì)于CFL和GQL，我們使用了[36]中提供的CFL和GQLfs的實(shí)現(xiàn)（GQLfs [36]在最先進(jìn)的標(biāo)記查詢(xún)算法中提供了最好的整體性能）。對(duì)于游隼、PBE-重用和GraphPi，我們從作者那里獲得了源代碼。對(duì)于PBE-重用，我們使用了它的多線程實(shí)現(xiàn)。對(duì)于LFTJ，我們通過(guò)嚴(yán)格遵循[41]中的規(guī)范（包括三次迭代器接口和連接邏輯）來(lái)實(shí)現(xiàn)該算法。由于LFTJ沒(méi)有指定匹配順序，我們使用GQL的匹配順序來(lái)運(yùn)行LFTJ，因?yàn)镚QL的排序策略在最先進(jìn)的子圖匹配方法[36]中是最有效的。[41]不討論其他查詢(xún)優(yōu)化（例如，自同構(gòu)處理）或如何并行化單線程算法，我們也實(shí)現(xiàn)了LFTJ的連接邏輯（不使用特里迭代器關(guān)系，但優(yōu)化直接訪問(wèn)CSR）和禁用壓縮，我們表示這個(gè)實(shí)現(xiàn)LFTJ-Circinus。
由于LFTJ、CFL和GQL都是單線程算法，所以我們通過(guò)在一個(gè)線程上運(yùn)行，將Circinus與它們進(jìn)行了比較。對(duì)于游隼、GraphPi、CBF和PBE-重用，我們?cè)谑褂盟?2個(gè)超線程的機(jī)器上與它們進(jìn)行了比較。對(duì)于CBF，我們使用推薦的每個(gè)容器1核和4 GB內(nèi)存，除了最大的數(shù)據(jù)集FR每個(gè)容器使用6GB內(nèi)存。

5.2.1 Results for Labeled Queries

對(duì)于標(biāo)記查詢(xún)，我們將Circinus與CFL [3]和GQL [16]進(jìn)行了比較，它們利用候選過(guò)濾規(guī)則和輔助數(shù)據(jù)結(jié)構(gòu)進(jìn)行查詢(xún)優(yōu)化，以及LFTJ。Circinus只使用一般模塊（即模塊1- 4）和模塊7，而Circinus-CFL和Circinus-GQL進(jìn)一步包括CFL和GQL的匹配順序和候選濾波策略（在模塊5-6中實(shí)現(xiàn)）。
單線程處理。圖5a報(bào)告了在HM和YT2上處理查詢(xún)集??8、??12和??16的六種方法的時(shí)間。我們使用標(biāo)準(zhǔn)的方框圖[43]來(lái)報(bào)告每一組查詢(xún)的時(shí)間。基于CFL/GQL的解決方案比LFTJ具有更多的優(yōu)勢(shì)，特別是在處理更復(fù)雜的查詢(xún)方面，這要感謝它們先進(jìn)的修剪策略。環(huán)組-CFL和GQL顯著提高了CFL和GQL的性能對(duì)于不同大小的查詢(xún)，我們可以回溯HM和YT2，盡管CFL和GQL都已經(jīng)有了先進(jìn)的優(yōu)化，通過(guò)匹配順序和候選過(guò)濾來(lái)減少冗余計(jì)算。通過(guò)與CFL/GQL進(jìn)行比較，我們發(fā)現(xiàn)環(huán)輪的計(jì)算共享明顯比CFL/GQL的候選濾波更有效，但其性能與YT2相當(dāng)。這是因?yàn)镠M是一個(gè)更密集的圖，它提供了更多的計(jì)算共享機(jī)會(huì)，因?yàn)橥唤M數(shù)據(jù)頂點(diǎn)可能出現(xiàn)在許多部分匹配中。
由于單個(gè)線程的計(jì)算能力不足，可能需要很長(zhǎng)時(shí)間來(lái)處理查詢(xún)，如果不能在1800秒內(nèi)完成，我們就殺死一個(gè)查詢(xún)（我們從圖5a中排除了CFL、GQL、LFTJ和Circinus無(wú)法完成的查詢(xún)）。表2報(bào)告了由每個(gè)方法完成的查詢(xún)的數(shù)量。在計(jì)算共享的幫助下，Circinus-CFL和Circinus-GQL完成了更多的查詢(xún)。
并行處理。然后，我們比較了環(huán)隼與LFTJ（實(shí)現(xiàn)）的并行查詢(xún)處理性能。然而，Peregrine不能在合理的時(shí)間內(nèi)處理更大的查詢(xún)，而且處理HM（HM的圖最小，但密度很大）和FR也需要太長(zhǎng)的時(shí)間。因此，我們選擇了YT2和OR，并使用了查詢(xún)集??6和??8。我們將在后續(xù)的實(shí)驗(yàn)中報(bào)告Circinus在更大的查詢(xún)和其他數(shù)據(jù)集上的結(jié)果。
圖5b報(bào)告了結(jié)果，其中所有的解決方案都使用了32個(gè)線程。游隼和游隼-cfl的性能都優(yōu)于游隼和LFTJ-游隼，而且它的速度比游隼快兩個(gè)數(shù)量級(jí)。游隼和圓直接對(duì)數(shù)據(jù)圖進(jìn)行回溯，而不使用復(fù)雜的候選濾波或輔助數(shù)據(jù)結(jié)構(gòu)。因此，圓比游隼的性能提高主要是由于基于壓縮組的回溯的計(jì)算共享。雖然圓沒(méi)有提供LFTJ-圓的最壞情況最優(yōu)保證，但圓的性能明顯優(yōu)于LFTJ，因?yàn)閳A具有基于實(shí)際成本模型的計(jì)算共享優(yōu)勢(shì)（見(jiàn)3.5節(jié)中關(guān)于最壞情況最優(yōu)連接的討論）。
Circinus甚至優(yōu)于Circinus-CFL（也叫Circinus-GQL），這是因?yàn)镃FL候選生成的開(kāi)銷(xiāo)大于CFL帶來(lái)的好處。Circinus對(duì)HM/YT2和OR的不同性能可以用數(shù)據(jù)圖中的標(biāo)簽分布來(lái)解釋。HM和YT2的標(biāo)簽分布呈偏態(tài)分布，而OR的標(biāo)簽分布呈均勻分布。因此，在OR的情況下，CFL/GQL的復(fù)雜濾波規(guī)則幾乎不比簡(jiǎn)單的基于標(biāo)簽/度的濾波具有更強(qiáng)的剪枝能力。

5.2.2 Results for Unlabeled Queries

圖6報(bào)告了未標(biāo)記查詢(xún)的執(zhí)行時(shí)間。我們對(duì)LFTJ和Circinus使用了相同的匹配順序。一些基線系統(tǒng)可能需要很長(zhǎng)時(shí)間來(lái)處理查詢(xún)，因?yàn)槲礃?biāo)記查詢(xún)的匹配數(shù)量可能非常大。因此，當(dāng)處理查詢(xún)超過(guò)12小時(shí)時(shí)，我們殺死了它。對(duì)于最大的圖FR，所有的系統(tǒng)都超過(guò)12小時(shí)，我們?cè)趫D6中省略了這些查詢(xún)的結(jié)果。圖6還跳過(guò)了??8對(duì)CBF的結(jié)果，因?yàn)镃BF需要手工優(yōu)化的MapReduce實(shí)現(xiàn)，并且我們只運(yùn)行它的內(nèi)置查詢(xún)（即??1-??7）。
在這些系統(tǒng)中，即環(huán)輪、GraphPi、LFTJ、PBE-重用、游隼和CBF，沒(méi)有單一的贏家。總的來(lái)說(shuō)，除了與GraphPi比較外，圓在大多數(shù)情況下都明顯優(yōu)于其他方法。對(duì)于小的無(wú)標(biāo)記查詢(xún)，圖的自同構(gòu)性和具有等價(jià)鄰域的查詢(xún)頂點(diǎn)是計(jì)算冗余性的主要因素。GraphPi通過(guò)其基于2周期的自同構(gòu)消除和計(jì)算避免技術(shù)解決了這些問(wèn)題。然而，雖然GraphPi是專(zhuān)門(mén)用于無(wú)標(biāo)記子圖匹配的最先進(jìn)的系統(tǒng)，但它的技術(shù)對(duì)標(biāo)記子圖匹配的影響有限。相比之下，Circinus對(duì)已標(biāo)記和未標(biāo)記的查詢(xún)都有良好的性能。PBE重用是一種基于緩存的方法，專(zhuān)門(mén)用于未標(biāo)記的子圖匹配，它通過(guò)生成一個(gè)執(zhí)行計(jì)劃來(lái)利用緩存集的交集結(jié)果來(lái)擴(kuò)展PBE [12]。然而，PBE重用在執(zhí)行過(guò)程中搜索緩存結(jié)果效率低，而且內(nèi)存占用也很大。CBF具有通過(guò)大規(guī)模物化重用計(jì)算的優(yōu)勢(shì)，但它存在高內(nèi)存占用和磁盤(pán)讀寫(xiě)開(kāi)銷(xiāo)。雖然物化三角形允許更多的計(jì)算重用，但開(kāi)銷(xiāo)可能超過(guò)好處，特別是在處理更小和更密集的查詢(xún)（例如，??1，??2，??5）。相比之下，游隼通過(guò)回溯在內(nèi)存使用方面是有效的，但由于第2節(jié)中分析的DFS方法的常見(jiàn)問(wèn)題，游隼存在很多冗余計(jì)算。特別是對(duì)于較大的查詢(xún)（例如，??6-??8），當(dāng)回溯搜索空間增大時(shí)，重復(fù)搜索空間迅速增加，游隼表現(xiàn)不佳。相比之下，Circinus既具有基于壓縮分組的回溯所帶來(lái)的內(nèi)存效率和計(jì)算共享的優(yōu)點(diǎn)，并具有最佳的整體性能。在大多數(shù)情況下，它的性能從游隼和CBF好幾倍到一個(gè)數(shù)量級(jí)。由于其基于壓縮的計(jì)算共享策略，圓環(huán)菌株的性能始終優(yōu)于LFTJ-Circinus。

5.2.3 Memory Usage Analysis

我們報(bào)告了我們?cè)谏鲜鰧?shí)驗(yàn)中比較的解決方案的峰值內(nèi)存消耗。結(jié)果（圖7和圖8）顯示，Circinus的內(nèi)存開(kāi)銷(xiāo)很小（并不比基于dfs的方法大多少，與BFS方法相比可以忽略不計(jì)）。
圖7a報(bào)告了與圖5a對(duì)應(yīng)的已標(biāo)記查詢(xún)的單線程處理的峰值內(nèi)存使用情況。與CFL和GQL相比，GQL、CFL和GQL在HM上的峰值記憶使用量相當(dāng)。圓環(huán)藻也有與DFS方法LFTJ相當(dāng)?shù)姆逯祪?nèi)存使用量。Circinus計(jì)算一個(gè)壓縮組，與DFS方法相比回溯的開(kāi)銷(xiāo)是由非頂點(diǎn)覆蓋查詢(xún)頂點(diǎn)的數(shù)量（即壓縮組中映射集的數(shù)量）乘以數(shù)據(jù)圖中的最大程度（即映射集的最大大?。Ｒ虼?，壓縮時(shí)的內(nèi)存開(kāi)銷(xiāo)通常很小。對(duì)于YT2，Circinus的內(nèi)存使用比CFL和GQL要少得多，因?yàn)镃ircinus避免了構(gòu)建輔助數(shù)據(jù)結(jié)構(gòu)（如4.2中所述）。CFL和GQL構(gòu)建了用于計(jì)算重用的輔助結(jié)構(gòu)，而YT2的輔助結(jié)構(gòu)的內(nèi)存占了90%以上的內(nèi)存使用，因?yàn)閅T2有一個(gè)偏態(tài)的標(biāo)簽分布。
圖7b和圖8報(bào)告了與圖5b和圖6對(duì)應(yīng)的并行處理的內(nèi)存使用峰值。從圖7b中可以看出，基于壓縮的解決方案（即環(huán)桂和環(huán)桂-cfl）在YT2上比基于dfs的解決方案（即游隼和LFTJ-環(huán)桂）有更多的內(nèi)存使用，但它們?cè)贠R上的內(nèi)存使用具有可比性。請(qǐng)注意，額外的內(nèi)存使用并不僅僅是由于壓縮，因?yàn)镃ircinus和LFTJ在單線程情況下具有類(lèi)似的內(nèi)存使用情況（圖7a），但這也是因?yàn)镃ircinus中的并行化機(jī)制。當(dāng)一個(gè)線程變得空閑并試圖從其他線程竊取工作時(shí)，Circinus會(huì)使運(yùn)行時(shí)間最長(zhǎng)的任務(wù)一次生成多個(gè)組。由于YT2有一個(gè)偏態(tài)分布，線程之間的負(fù)載往往是不平衡的。因此，任務(wù)分裂發(fā)生得更頻繁，并產(chǎn)生許多組，從而導(dǎo)致更高的內(nèi)存開(kāi)銷(xiāo)。然而，如圖8所示，與BFS方法（即PBE重用）相比，基于dfs的方法(Circinus對(duì)于較小的圖（YT、LJ，OR）的內(nèi)存使用可以忽略不計(jì)，而對(duì)于大圖FR的內(nèi)存使用也明顯較小。我們沒(méi)有在圖8中報(bào)告CBF的內(nèi)存使用情況，因?yàn)樗陂_(kāi)始時(shí)為容器分配了所有內(nèi)存，并且CBF有非常高的內(nèi)存需求以及磁盤(pán)I/O使用情況來(lái)處理BFS中的大量中間結(jié)果。因此，我們可以得出基于壓縮的方法的內(nèi)存開(kāi)銷(xiāo)是合理的，Circinus實(shí)現(xiàn)了內(nèi)存效率和計(jì)算共享的目標(biāo)。
在下面的部分中，我們將關(guān)注標(biāo)記查詢(xún)，因?yàn)橹挥猩倭康奈礃?biāo)記查詢(xún)的處理時(shí)間是可以接受的，也就是說(shuō)，只有某些小的查詢(xún)圖，而大多數(shù)查詢(xún)使用任何現(xiàn)有方法進(jìn)行處理都很昂貴。

5.3 Effectiveness of Redundancy Reduction

在這組實(shí)驗(yàn)中，我們首先證明了圓輪的性能增益主要來(lái)自于冗余計(jì)算的減少。然后，我們展示了哪些查詢(xún)大小和數(shù)據(jù)集的冗余減少更有效。我們計(jì)算每種情況下所需的集合交集的數(shù)量。圓輪和基線之間的交集計(jì)數(shù)的差異反映了保存的計(jì)算。
減少冗余的影響。圖9報(bào)告了C GQL、C GQL GQL、C GQL、CFL和GQL的回溯時(shí)間（不包括計(jì)劃和候選生成的時(shí)間）和交叉計(jì)數(shù)。圖9a中的回溯時(shí)間模式與圖9b中的交集計(jì)數(shù)相似，表明交集計(jì)數(shù)對(duì)回溯時(shí)間有直接影響。需要注意的是，Circinus-CFL/GQL采用了與CFL/GQL相同的候選過(guò)濾策略和匹配順序，這導(dǎo)致了類(lèi)似的回溯搜索空間。交集計(jì)數(shù)的差異主要來(lái)自于Circinus的基于壓縮組的回溯。結(jié)果表明，驗(yàn)證了基于壓縮組的回溯是一種有效的冗余減少技術(shù)，是CFL和GQL性能提高的主要因素。
冗余減少程度。我們還評(píng)估了圓圈減少重復(fù)計(jì)算的程度。我們對(duì)標(biāo)記查詢(xún)using??8運(yùn)行CFL和GQL，對(duì)未標(biāo)記查詢(xún)??1和??3運(yùn)行游隼。我們報(bào)告了圖114中的交集計(jì)數(shù)和相應(yīng)的最優(yōu)交集計(jì)數(shù)，通過(guò)消除在回溯的每個(gè)級(jí)別上的所有重復(fù)計(jì)算，可以實(shí)現(xiàn)這些計(jì)數(shù)。我們已經(jīng)討論了第2節(jié)中的結(jié)果，以驗(yàn)證我們的觀察結(jié)果。雖然使用基于dfs的方法很難實(shí)現(xiàn)最優(yōu)數(shù)字，但與基線相比，Circinus有效節(jié)省了96.45%的冗余計(jì)算，標(biāo)記情況下平均節(jié)省了87.30%的冗余計(jì)算。
對(duì)查詢(xún)大小和數(shù)據(jù)圖的敏感性。我們?cè)贑ircinus中禁用了基于vc的組壓縮，如圖10中的Circinus表示，并評(píng)估了基于不同的組vc壓縮對(duì)查詢(xún)性能的影響。CFL和GQL的候選過(guò)濾和匹配順序也被啟用，如圖10中??軸上的CFL和GQL所標(biāo)記。圖10a-10d顯示，在所有查詢(xún)大小和數(shù)據(jù)圖中，Circinus的性能顯著優(yōu)于Circinus，從而驗(yàn)證了基于vc的組壓縮的有效性。結(jié)果還表明，減少的冗余度（即從圓環(huán)到圓環(huán)的交點(diǎn)計(jì)數(shù)的減少）有效地轉(zhuǎn)化為圓環(huán)的性能增益（即縮短的回溯時(shí)間）。
圖10b顯示，基于vc的組壓縮可以為更大的查詢(xún)減少更多的交叉，這也導(dǎo)致圖10a中的回溯時(shí)間更大的減少（注意，??軸是對(duì)數(shù)尺度的）。圖10d進(jìn)一步顯示，減少十字路口的更大的數(shù)據(jù)集（即FR）和數(shù)據(jù)集與傾斜標(biāo)簽分布（即YT2），和圖10c顯示查詢(xún)這些數(shù)據(jù)集也更昂貴的過(guò)程和顯著減少交集數(shù)量反映在一個(gè)巨大的減少回溯時(shí)間。

5.4 Influence of Vertex Covers

我們通過(guò)與一種使用輸入查詢(xún)圖??的最小權(quán)重VC進(jìn)行壓縮的替代方法（用圖12中的MWVC表示）進(jìn)行比較，來(lái)評(píng)估Circinus的VC選擇方法的質(zhì)量。MWVC通過(guò)相交于最小權(quán)重來(lái)計(jì)算??的每個(gè)子查詢(xún)????的VC??的頂點(diǎn)集為????的頂點(diǎn)集。圖12報(bào)告了MWVC和Circinus的回溯時(shí)間。Circinus在所有數(shù)據(jù)集和查詢(xún)方面都優(yōu)于MWVC。請(qǐng)注意，MWVC實(shí)際上優(yōu)化了輸出的壓縮比。相比之下，圓輪選擇風(fēng)投的目標(biāo)是設(shè)定交集的減少。

5.5 Sensitivity to ????????????(?? ) Estimation

我們比較了????????????（??）的兩種估計(jì)方法： (1)通過(guò)基于CFL和GQL構(gòu)造的輔助數(shù)據(jù)結(jié)構(gòu)，計(jì)算樹(shù)狀路徑權(quán)值，用CFLPath和GQL-Path表示；(2)計(jì)算??中查詢(xún)??中候選頂點(diǎn)的基數(shù)的乘積，用GQL積表示。為簡(jiǎn)單起見(jiàn)，這里我們使用CFL/GQL來(lái)引用Circinus-CFL/GQL。我們想證明一個(gè)簡(jiǎn)單而有效的估計(jì)方法，如乘積，也是有效的。
圖13報(bào)告了在四個(gè)數(shù)據(jù)集上運(yùn)行??8和??12的回溯時(shí)間。盡管使用路徑權(quán)值來(lái)估計(jì)????????????（??）比使用乘積更準(zhǔn)確，但對(duì)于我們的目的來(lái)說(shuō)，不那么準(zhǔn)確的估計(jì)并不一定是不那么有效的。事實(shí)上，對(duì)于大多數(shù)查詢(xún)，所選的VC序列使用其中的任何一種估計(jì)方法都是相同的。這是因?yàn)椴煌??的????????????（??）的差異主要由??的大小決定，而不管使用的路徑權(quán)重或產(chǎn)品，因?yàn)榇蠖鄶?shù)查詢(xún)頂點(diǎn)都有大量的匹配。因此，在方程1中，????????????（??∪{??}）通常比????????????（??）大得多，因此最小化代價(jià)會(huì)導(dǎo)致選擇一個(gè)更小的頂點(diǎn)覆蓋??，它與父頂點(diǎn)集??有更多的交集。

5.6 Performance of Parallelization

我們通過(guò)將線程的數(shù)量從1改變到32來(lái)評(píng)估Circinus的性能，用于處理最大數(shù)據(jù)集FR上的查詢(xún)集??16。圖14a報(bào)告了在單個(gè)線程上使用多個(gè)線程的執(zhí)行時(shí)間的加速。Circinus實(shí)現(xiàn)了多達(dá)8個(gè)線程的幾乎線性可伸縮性，然后加速速度從8個(gè)線程減慢到16個(gè)線程。可伸縮性的退化可以用我們的機(jī)器中的硬件來(lái)解釋?zhuān)?6個(gè)物理內(nèi)核（32個(gè)超線程），每個(gè)套接字有8個(gè)內(nèi)核。當(dāng)Circinus使用超過(guò)8個(gè)線程時(shí)，就使用了兩個(gè)以上的套接字，因此性能會(huì)受到NUMA效應(yīng)的影響。此外，當(dāng)使用超過(guò)16個(gè)線程時(shí)，由于超線程，計(jì)算能力不會(huì)比使用更多的物理核增加那么多。
圖14b報(bào)告了峰值內(nèi)存消耗（標(biāo)記為峰值）和用于存儲(chǔ)輸入圖的內(nèi)存（標(biāo)記為圖）。通過(guò)基于壓縮組的回溯，Circinus在查詢(xún)處理中實(shí)現(xiàn)了較小的內(nèi)存使用（即，峰值和圖之間的差異）。當(dāng)線程從1增加到16時(shí)，峰值內(nèi)存緩慢增加，當(dāng)線程數(shù)進(jìn)一步增加到32時(shí)，峰值內(nèi)存保持在29.56GB左右。結(jié)果表明，循環(huán)性能穩(wěn)定，內(nèi)存使用量低。

6 RELATED WORK

圖形挖掘系統(tǒng)。有幾個(gè)圖挖掘系統(tǒng)支持已標(biāo)記/未標(biāo)記的子圖匹配[7,11,17,24,38,42,44]（在這里，我們排除了那些不支持子圖匹配的圖挖掘系統(tǒng)）。阿拉伯式的[38]提供了用于指定挖掘過(guò)程的高級(jí)api，并提出了“像嵌入一樣思考”的概念。G-Miner [7]、G-思想家[44]和RStream [42]采用了類(lèi)似于阿拉伯式的高級(jí)抽象。G-Miner提出了一個(gè)面向任務(wù)的處理框架來(lái)優(yōu)化內(nèi)存使用和提高處理速度。G-fisher為用戶(hù)提供了一個(gè)直觀的圖形探索API來(lái)實(shí)現(xiàn)圖形挖掘算法，并通過(guò)在基于磁盤(pán)的優(yōu)先級(jí)隊(duì)列中緩沖多余的任務(wù)來(lái)解決高內(nèi)存使用問(wèn)題。RStream是第一個(gè)單機(jī)、核外圖挖掘系統(tǒng)，它具有一組關(guān)系代數(shù)操作，將挖掘任務(wù)表示為關(guān)系連接。正如在[24]中所指出的，上述四個(gè)系統(tǒng)由于其類(lèi)似于BFS的執(zhí)行方法，仍然存在很高的內(nèi)存使用量，因此計(jì)算效率低下。AutoMine [24]、分形[11]和游隼[17]是最新的圖形挖掘系統(tǒng)，它們采用了DFS方法來(lái)有效地使用內(nèi)存。分形將“像嵌入一樣思考”擴(kuò)展到分形，以允許邊緣誘導(dǎo)、頂點(diǎn)誘導(dǎo)的智能規(guī)劃或模式誘導(dǎo)的執(zhí)行。AutoMine提出了一種基于集的表示來(lái)節(jié)省空間，并為其代碼生成的編譯技術(shù)提供了基礎(chǔ)。游隼提供了一個(gè)基于反邊/頂點(diǎn)語(yǔ)義的基于模式的編程模型。游隼也采用了AutoMine的集合表示。在這些系統(tǒng)中，游隼和分形利用自同構(gòu)消去來(lái)減少子圖匹配的計(jì)算冗余。我們?cè)诘?節(jié)中比較了Circinus和游隼，因?yàn)樗且粋€(gè)最近的圖形挖掘系統(tǒng)，并已被證明優(yōu)于其他系統(tǒng)[7,11,38,42]。
子圖匹配系統(tǒng)和算法。與圖挖掘系統(tǒng)相比，專(zhuān)門(mén)的子圖匹配系統(tǒng)提供了更復(fù)雜的優(yōu)化。圖零[23]利用群理論改進(jìn)了自挖掘來(lái)打破查詢(xún)圖中的對(duì)稱(chēng)性，以實(shí)現(xiàn)自同構(gòu)消除。它允許通過(guò)要求更高程度的頂點(diǎn)具有更小的id來(lái)對(duì)任意模式進(jìn)行方向優(yōu)化。GraphPi [34]通過(guò)生成多個(gè)自同構(gòu)消除的偏階改進(jìn)了圖零，并使用代價(jià)模型聯(lián)合選擇匹配的階和偏階。GraphPi還在頂點(diǎn)集上使用包含-不相容原理來(lái)優(yōu)化子圖計(jì)數(shù)。PBE [12]和穿山甲[8]利用GPU來(lái)加速計(jì)算。穿山甲提出了一種用于GPU處理的高級(jí)擴(kuò)展-簡(jiǎn)化-過(guò)濾器模型，并使用了一種基于BFS的方法來(lái)利用GPU的并行性。PBE建議分區(qū)數(shù)據(jù)圖和共享執(zhí)行方法來(lái)找到分區(qū)間匹配。PBE-repes[13]通過(guò)基于緩存的方法擴(kuò)展PBE重用集交叉結(jié)果，并提供了GPU和CPU多線程實(shí)現(xiàn)。HUGE [46]和aDFS [39]可以在BFS和DFS之間切換，以在內(nèi)存效率和并行性之間取得平衡。HUGE是一個(gè)基于分布式連接的分布式框架，具有推拉混合通信模型。它側(cè)重于優(yōu)化分布式（散列和最壞情況下最優(yōu)）連接操作。當(dāng)需要更多的本地并行工作時(shí)，aDFS使用異步的基于dfs的回溯來(lái)綁定內(nèi)存消耗，并在相同的回溯級(jí)別上切換到BFS。
目前已經(jīng)提出了許多子圖匹配算法。我們只討論最相關(guān)的問(wèn)題，并讓讀者參考最近的調(diào)查[36]。GQL[16]，Turbo??????[15]，CFL [3]，CECI [2]，DAF [14]和VEQ [20]通過(guò)遵循“預(yù)處理-枚舉”[36]方法來(lái)修剪回溯搜索空間來(lái)支持標(biāo)記查詢(xún)。它們首先使用各種過(guò)濾規(guī)則為每個(gè)查詢(xún)頂點(diǎn)生成一個(gè)候選集，然后構(gòu)建一個(gè)輔助數(shù)據(jù)結(jié)構(gòu)，它由對(duì)應(yīng)于查詢(xún)邊的二部圖組成。在輔助數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上，采用啟發(fā)式方法選擇匹配順序并進(jìn)行回溯。Turbo??????根據(jù)頂點(diǎn)鄰域集的等價(jià)性來(lái)壓縮查詢(xún)圖，以進(jìn)行重用計(jì)算。Boost??????[30]通過(guò)壓縮基于鄰集等價(jià)集的數(shù)據(jù)圖，以減少計(jì)算冗余。SEED [21]和CBF [28]支持遵循基于連接的方法[1]的無(wú)標(biāo)記查詢(xún)，并在MapReduce上實(shí)現(xiàn)。SEED在數(shù)據(jù)圖中預(yù)先計(jì)算一組不重疊的團(tuán)團(tuán)來(lái)進(jìn)行壓縮，以避免部分匹配的物化。CBF提出了一種基于vc的壓縮技術(shù)，以降低輸出和存儲(chǔ)子圖匹配的成本，并通過(guò)連接邊和團(tuán)系來(lái)計(jì)算匹配。
與現(xiàn)有的子圖匹配系統(tǒng)和算法相比，Circinus解決一個(gè)內(nèi)在的問(wèn)題重復(fù)計(jì)算基于回溯的子圖匹配[2、3、11、12、14-17、23日，24、34、39、41、46]，我們?cè)诘?節(jié)表明，我們的方法明顯優(yōu)于最先進(jìn)的方法[3,12,16,17,28,36]。Circinus也是一個(gè)通用的框架，它允許靈活地組合許多優(yōu)化技術(shù)，來(lái)優(yōu)化不同的數(shù)據(jù)集和查詢(xún)集的處理。
使用壓縮和頂點(diǎn)覆蓋。Boost??????[30]和SEED [21]使用數(shù)據(jù)圖壓縮來(lái)減少計(jì)算冗余，但它們有很大的預(yù)處理成本，而且好處需要特殊的局部結(jié)構(gòu)（例如，許多具有相似鄰居或大的團(tuán)的頂點(diǎn)）。圓圈減少計(jì)算預(yù)余不需要預(yù)處理，因?yàn)樗诨厮葸^(guò)程中實(shí)時(shí)壓縮部分匹配，因此可以用于動(dòng)態(tài)圖處理。游隼[17]使用VC來(lái)減少同構(gòu)檢查開(kāi)銷(xiāo)，CBF [28]使用最小的VC壓縮輸出子圖以節(jié)省磁盤(pán)寫(xiě)入和存儲(chǔ)成本，而PBE [12]使用VC來(lái)延遲部分匹配的物化。他們對(duì)VC的使用不同于Circinus，后者使用VC對(duì)部分匹配進(jìn)行分組以進(jìn)行計(jì)算共享，并取得了比第5.2節(jié)中報(bào)道的游隼、CBF和PBE更好的性能。
圖形數(shù)據(jù)庫(kù)系統(tǒng)。圖數(shù)據(jù)庫(kù)[6,10,29,37]支持同構(gòu)或同態(tài)子圖匹配的不同語(yǔ)義。它們采用屬性圖模型，并支持Cypher和Gremlin等查詢(xún)語(yǔ)言。與上述同構(gòu)子圖匹配解決方案不同，其工作負(fù)載具有復(fù)雜的查詢(xún)拓?fù)浜兔芗娜珗D訪問(wèn)，屬性圖數(shù)據(jù)庫(kù)是為具有選擇性屬性過(guò)濾器和簡(jiǎn)單查詢(xún)拓?fù)涞奶卣鳎ɡ纾餍械腖DBC基準(zhǔn)測(cè)試）的工作負(fù)載設(shè)計(jì)的。因此，雙方采用了非常不同的技術(shù)。具體來(lái)說(shuō)，處理類(lèi)似LDBC的工作負(fù)載的系統(tǒng)的性能在很大程度上取決于圖形數(shù)據(jù)庫(kù)的索引設(shè)計(jì)和圖形布局。例如，Neo4J [37]支持單個(gè)或多個(gè)屬性上的b-樹(shù)索引，以加速頂點(diǎn)/邊的檢索。重構(gòu)圖[29]支持單屬性索引。它通過(guò)邊標(biāo)簽對(duì)圖的鄰接矩陣進(jìn)行分區(qū)，并表示內(nèi)存中CSR中的每個(gè)分區(qū)，以允許對(duì)具有特定標(biāo)簽的邊進(jìn)行快速的基于線性代數(shù)的遍歷。TigerGraph [10]對(duì)屬性圖應(yīng)用同態(tài)編碼進(jìn)行緊湊存儲(chǔ)，允許快速的單頂點(diǎn)/邊檢索和索引更新。Grasper [6]在分布式集群中劃分一個(gè)屬性圖，并通過(guò)基于RDMA的本地圖存儲(chǔ)設(shè)計(jì)優(yōu)化對(duì)圖拓?fù)浜蛯傩缘脑L問(wèn)?？傊?，雖然同構(gòu)子圖匹配解和圖數(shù)據(jù)庫(kù)的核心工作是相同的問(wèn)題，但它們被設(shè)計(jì)用于處理具有不同特征的查詢(xún)。

7 CONCLUSIONS

我們提出了一種子圖匹配系統(tǒng)，它提供了一種新的基于壓縮的方法來(lái)減少回溯過(guò)程中的計(jì)算冗余。該方法可與現(xiàn)有的優(yōu)化技術(shù)結(jié)合應(yīng)用，如CFL、GQL和 Peregrine。我們的實(shí)驗(yàn)結(jié)果表明，Circinus在保持低內(nèi)存占用的同時(shí)顯著減少了重復(fù)計(jì)算，這將轉(zhuǎn)移到比最先進(jìn)的解決方案更好的性能好幾個(gè)數(shù)量級(jí)。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-775205.html

到了這里，關(guān)于【論文閱讀】Circinus: Fast Redundancy-Reduced Subgraph Matching的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！