劉小軒

摘 ?要： 針對傳統(tǒng)圖模式查詢算法難以實現(xiàn)在大圖數(shù)據(jù)上查詢或查詢時間太長問題，提出基于MapReduce的圖查詢并行算法PGPQ。該方法包括計算初始匹配節(jié)點集、初始不匹配父親節(jié)點集和圖模式查詢?nèi)齻€部分。在圖模式查詢過程利用初始不匹配父親節(jié)點集迭代初始匹配節(jié)點集中的節(jié)點，如果數(shù)據(jù)圖匹配模式圖，返回一個最大的匹配。實驗結(jié)果表明，PGPQ算法查詢能有效地進行大圖模式查詢。

關(guān)鍵詞： 并行處理; 圖模式查詢; 圖模式匹配; 大圖數(shù)據(jù); MapReduce; 實驗驗證

中圖分類號： TN911.1?34; TP311 ? ? ? ? ? ? ? ? ? ? 文獻標識碼： A ? ? ? ? ? ? ? ? ?文章編號： 1004?373X（2019）20?0045?03

Parallel graph query for large graph data

LIU Xiaoxuan

（School of Control and Computer Engineering， North China Electric Power University， Beijing 102206， China）

Abstract： As the traditional pattern graph query algorithm has the problem that it is difficult to query big graph data or the query time is too long， a parallel graph query algorithm PGPQ based on MapReduce is proposed. The method includes three parts： computation of the initial matched node set， the initial mismatched father node set and graph pattern query. In the graph pattern query process， the initial mismatched parent node set is used to iterate the nodes in the initial matching node set. If the data graph matches the pattern graph， a maximum match is returned. The experimental results show the query of PGPQ algorithm can effectively perform big graph pattern query.

Keywords： parallel processing; graph pattern query; graph pattern matching; large graph data; MapReduce; experimental verification

0 ?引 ?言

在過去的幾十年中，圖查詢已經(jīng)得到了廣泛的研究，包括圖可達性查詢[1]和圖模式匹配[2]。一些方法，如基于跳的方法[3?4]和基于覆蓋的方法[5?6]經(jīng)常被采用。它們之間的區(qū)別是如何構(gòu)建互補的索引，該編碼將編碼的剩余可達性信息編碼在基蓋之外?；谔姆椒ㄍǔ＞哂斜然诟采w的方法小得多的索引大小，并且將基于跳的可達性索引集成到其他索引框架（如圖模式匹配）[7]中更簡單。

圖模式匹配在不同領(lǐng)域中被證明是有用的[8]，目前已經(jīng)通過子圖同構(gòu)提出了幾種算法。還有一些基于圖模擬的一些方法[9?12]。文獻[10]研究了基于圖模擬的模式圖，它考慮了路徑的有界長度和節(jié)點屬性約束和搜索條件的節(jié)點。文獻[11]提出了一種弱相似性的概念，該方法通過將邊映射到無界的路徑，從而擴展了圖模擬，它關(guān)注子圖相似度，是一個NP?hard問題。文獻[12]在模式圖中考慮有界連通性，其中模式在所有邊上施加相同的邊界，并且基于子圖同構(gòu)的擴展來進行圖匹配，這仍然是NP?hard問題。

近年來，已經(jīng)有些基于大圖數(shù)據(jù)的圖查詢的研究[13?14]。文獻[13]解決了大型網(wǎng)絡(luò)中的圖查詢優(yōu)化問題，文獻[14]中對查詢的尺度無關(guān)性的概念進行了形式化。為了使查詢響應(yīng)在大數(shù)據(jù)集中可行，文獻[15?16]中提出了一些并行圖匹配方法。文獻[15]提出了一種圖模擬的分布式算法，通過首先計算部分匹配，增強了數(shù)據(jù)模擬的數(shù)據(jù)局部性，從而優(yōu)化了數(shù)據(jù)傳輸和查詢時間。然而，強連通分量在圖匹配期間會導(dǎo)致較差的數(shù)據(jù)局部性，因為只有在強連通分量中的G的所有節(jié)點都在一個機器內(nèi)時，才可以執(zhí)行圖G上的匹配。文獻[16]提出了一種強模擬的分布式算法[17]，首先使網(wǎng)絡(luò)流量可控，保證了強模擬的更低時間復(fù)雜度。文獻[10]中的工作，通過放寬子圖同構(gòu)條件提出一種立方時間內(nèi)圖模式匹配方法。文獻[17]提出基于六度分隔理論的可達索引，為圖中每一個點建立一個六度可達索引，解決局部查詢問題。因為實際應(yīng)用中絕大多數(shù)應(yīng)用查詢都應(yīng)該在六度以內(nèi)。本文通過使用文獻[17]中六度可達索引，基于MapReduce對文獻[10]中的圖匹配算法并行化，以實現(xiàn)在大圖數(shù)據(jù)上高效的圖模式查詢。

1 ?圖模式匹配

首先簡要地給出了文獻[10]中關(guān)于圖模式查詢的初步研究，并且使用mat（）記錄初始匹配節(jié)點集，使用premv（）記錄初始不匹配父親節(jié)點集，使用desc（）記錄后代節(jié)點，使用anc（）記錄祖先節(jié)點集。

定義1 數(shù)據(jù)圖。G（V，E，fA）是一個有向圖。V表示數(shù)據(jù)圖G上所有的節(jié)點集合;E表示數(shù)據(jù)圖G上所有的有向邊集合，[E?V×V];fA是定義在V上的一個函數(shù)，對于每一個節(jié)點v，[v∈V]，fA（v）表示節(jié)點v的屬性元組，fA（v）={A1=a1，a2，…，An=an}，對于每一個元組“Ai=ai”，表示節(jié)點v有一個屬性為Ai，屬性值為ai。在G中一條路徑是一系列v1/…/vn的節(jié)點，其中（vi，vi+1）是在G中的一條邊，[i∈[1，n-1]]，把v2稱為v1的孩子（或v1是v2的父親），vi是v1的后代節(jié)點，i∈[2，n]。

定義2 模式圖。P（Vp，Ep，fe，fv）為模式圖。Vp表示P上的節(jié)點集;Ep表示有向邊集;fe是一個定義在Ep（u，u）上的函數(shù)，表示有向邊（u′，u）在G中對應(yīng)的有向路徑（v′，v）的長度的約束限制;fv是一個定義在Vp上的一個函數(shù)，對于P中的每一個節(jié)點u，fv（u）表示結(jié)果圖G′中與u匹配的節(jié)點的屬性應(yīng)該滿足的條件。對于每個屬性條件限制使用的“A op a”的形式，其中A代表某個屬性;op代表操作符{<，>，=，<=，>=，！=，has}，a代表屬性值。

定義3 有界的圖模擬。給定數(shù)據(jù)圖G=（V，E，fA）和模式圖P=（Vp，Ep，fe，fv），如果存在一個二元關(guān)系[R?V×Vp]，通過有界的模擬，滿足以下條件，則G匹配P。

1） 對Vp中每個節(jié)點u，在V中存在v使得（u，v）∈R。

2） 對每一個（u，v）∈R，v的屬性fA（v）滿足u的謂詞fv（u），也就是說，在fv（u）對于每個原子公式“A op a”，在fA（v）上定義v，A=a′，而且“a′ op a”;對于Ep中的每條邊（u， u′），G中存在非空路徑p=v/…/v′，如果fe（u，u′）是常數(shù)k，使得（u，u′）∈R和len（p）≤k。

定義4 ?mat（u）。讓G=（V，E，fA）是一個數(shù)據(jù)圖并且P=（Vp，Ep，fe，fv）是一個模式圖。對Vp中任意節(jié)點u， mat（u）={x|x∈V，fA（x）滿足fv（u）， 并且 out?degree（x）≠0 if out?degree （u）≠0}。

定義5 ?premv（u）。讓G=（V，E，fA）是一個數(shù)據(jù)圖并且P=（Vp，Ep，fe，fv）是一個模式圖。對Vp中任意節(jié)點， premv（u）={x|x∈V，out?degree（x）≠0， 并且存在（u′，u）∈Ep（x′∈mat（u），fA（x）滿足fv（u′），并且len（x/…/x′）≤fe（u′， u））}。

定義6 ?anc（x）。讓G=（V，E，fA）是一個數(shù)據(jù)圖并且P=（Vp，Ep，fe，fv）是一個模式圖。對集合V任意節(jié)點x， anc（x）={x′|x′∈V，（u′，u）∈Ep（fA（x）滿足fv（u），fA（x′）滿足fv（u′）并且len（x′…x） ≤fe（u′， u））}。

定義7 ?desc（x）。讓G=（V，E，fA）是一個數(shù)據(jù)圖并且P=（Vp，Ep，fe，fv）是一個模式圖。對集合V任意節(jié)點x， desc（x） ={x′|x′∈V，（u′，u）∈Ep（fA（x）滿足fv（u），fA（x′）滿足fv（u′）并且len（x′…x） ≤fe（u′，u））}。

2 ?并行圖模式查詢算法流程（PGPQ）

在PGPQ算法中使用MRS（Matched Result Set）記錄匹配結(jié)果集。PGPQ算法包括兩個階段：第一個匹配預(yù)處理階段計算mat（）和計算premv（）;第二個圖查詢階段計算MRS（）。PGPQ算法流程如圖1所示。首先，計算初始匹配節(jié)點集;然后，計算初始不匹配父節(jié)點的節(jié)點集;最后，使用premv（）不斷地清洗mat（）中不滿足條件的節(jié)點，返回匹配結(jié)果集為空集或為最大的匹配。

圖1 ?算法流程

3 ?實驗分析

3.1 ?實驗數(shù)據(jù)及環(huán)境

本文使用以下幾個實際應(yīng)用中的數(shù)據(jù)集，其中數(shù)據(jù)集分別是：Patent數(shù)據(jù)集[18] 、DBLP數(shù)據(jù)集和YouTube數(shù)據(jù)集。

表1 ?數(shù)據(jù)集

Hadoop集群基于Ubuntu系統(tǒng)，使用VMware Workstation搭建，由8個虛擬機組成分布式并行計算環(huán)境，其中8臺物理機通過100 Mb/s路由器連接。

3.2 ?實驗結(jié)果

實驗部分對PGPQ算法加速比進行了評估，還對比了兩種不同的距離探測方法（基于六度可達索引的查詢和基于BFS算法在線距離探測的查詢）。此外，六度可達索引離線建立，不計入查詢時間。對于模式圖使用P（x，y，z）表示，x表示模式的節(jié)點數(shù)Vp，y表示模式的邊數(shù)Ep，z表示k跳數(shù)。

3.2.1 ?PGPQ算法加速比分析

對于加速比評估，分別采用1，2，4和8個節(jié)點對不同數(shù)據(jù)集中的使用模式圖P（6，6，3）查詢，并記錄有效的運行時間。PGPQ加速比如圖2所示。

圖2 ?PGPQ算法加速比

[11] NARDO L D， RANZATO F， TAPPARO F. The subgraph similarity problem [J]. IEEE transactions on knowledge & data engineering， 2008（5）： 748?749.

[12] ZOU L， CHEN L， ZSU M T. Distance?join： pattern match query in a large graph database [J]. VLDB endowment，2009， 2（1）： 886?897.

[13] ZHAO P X， HAN J W. On graph query optimization in large networks [J]. Proceedings of the VLDB endowment， 2010， 3（1/2）： 340?351.

[14] FAN W， GEERTS F， LIBKIN L. On scale independence for querying big data [C]// ACM Symposium on Principles of Database Systems. Snowbird ?Utah： ACM， 2014： 51?62.

[15] MA S， CAO Y， HUAI J P， et al. Distributed graph pattern matching [C]// Proceedings of 21st Annual Conference on World Wide Web. Lyon： [s.n.]， 2012： 949?958.

[16] WANG H Z， LI N， LI J Z， et al. Parallel algorithms for flexible pattern matching on big graphs [J]. Information sciences， 2018， 436/437： 418?440.

[17] 高延太.基于并行處理大數(shù)據(jù)圖查詢研究[D].北京：華北電力大學(xué)，2017.

GAO Yantai. Research on graph query of large data based on parallel processing [D]. Beijing： North China Electric Power University， 2017.

[18] National Research Council of the National Academies. Frontiers in massive data analysis [M]. Washington： The National Academies Press， 2013.