面向大圖數(shù)據(jù)的并行圖查詢

劉小軒

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

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

中圖分類號(hào)： TN911.1?34; TP311 ? ? ? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼： A ? ? ? ? ? ? ? ? ?文章編號(hào)： 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)得到了廣泛的研究，包括圖可達(dá)性查詢[1]和圖模式匹配[2]。一些方法，如基于跳的方法[3?4]和基于覆蓋的方法[5?6]經(jīng)常被采用。它們之間的區(qū)別是如何構(gòu)建互補(bǔ)的索引，該編碼將編碼的剩余可達(dá)性信息編碼在基蓋之外。基于跳的方法通常具有比基于覆蓋的方法小得多的索引大小，并且將基于跳的可達(dá)性索引集成到其他索引框架（如圖模式匹配）[7]中更簡(jiǎn)單。

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

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

1 ?圖模式匹配

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

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

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

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

1） 對(duì)Vp中每個(gè)節(jié)點(diǎn)u，在V中存在v使得（u，v）∈R。

2） 對(duì)每一個(gè)（u，v）∈R，v的屬性fA（v）滿足u的謂詞fv（u），也就是說，在fv（u）對(duì)于每個(gè)原子公式“A op a”，在fA（v）上定義v，A=a′，而且“a′ op a”;對(duì)于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）是一個(gè)數(shù)據(jù)圖并且P=（Vp，Ep，fe，fv）是一個(gè)模式圖。對(duì)Vp中任意節(jié)點(diǎn)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）是一個(gè)數(shù)據(jù)圖并且P=（Vp，Ep，fe，fv）是一個(gè)模式圖。對(duì)Vp中任意節(jié)點(diǎn)， 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）是一個(gè)數(shù)據(jù)圖并且P=（Vp，Ep，fe，fv）是一個(gè)模式圖。對(duì)集合V任意節(jié)點(diǎn)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）是一個(gè)數(shù)據(jù)圖并且P=（Vp，Ep，fe，fv）是一個(gè)模式圖。對(duì)集合V任意節(jié)點(diǎn)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算法包括兩個(gè)階段：第一個(gè)匹配預(yù)處理階段計(jì)算mat（）和計(jì)算premv（）;第二個(gè)圖查詢階段計(jì)算MRS（）。PGPQ算法流程如圖1所示。首先，計(jì)算初始匹配節(jié)點(diǎn)集;然后，計(jì)算初始不匹配父節(jié)點(diǎn)的節(jié)點(diǎn)集;最后，使用premv（）不斷地清洗mat（）中不滿足條件的節(jié)點(diǎn)，返回匹配結(jié)果集為空集或?yàn)樽畲蟮钠ヅ洹?h3>圖1 ?算法流程

3 ?實(shí)驗(yàn)分析

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

本文使用以下幾個(gè)實(shí)際應(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個(gè)虛擬機(jī)組成分布式并行計(jì)算環(huán)境，其中8臺(tái)物理機(jī)通過100 Mb/s路由器連接。

3.2 ?實(shí)驗(yàn)結(jié)果

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

3.2.1 ?PGPQ算法加速比分析

對(duì)于加速比評(píng)估，分別采用1，2，4和8個(gè)節(jié)點(diǎn)對(duì)不同數(shù)據(jù)集中的使用模式圖P（6，6，3）查詢，并記錄有效的運(yùn)行時(shí)間。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.