清华大学 计算机科学与技术系, 信息科学与技术国家实验室, 北京 100084
收稿日期: 2016-01-29
基金项目: 国家“八六三”高技术项目（2015AA020102）
作者简介: 兰超(1989-),男,博士研究生。
通讯作者: 邢春晓,研究员,E-mail:xingcx@tsinghua.edu.cn
摘要：Top-k子图匹配是一种应用广泛的图搜索技术。相比于单机环境，分布式环境下的Top-k子图匹配问题具有更大的挑战性。该文分析了已有方法在分布式环境下存在的问题，提出了包括查询拆分、查询执行、结果连接3个步骤的算法。算法通过查询拆分，彻底避免了生成中间结果过程中的数据传输，同时通过优化查询执行和结果连接步骤，避免不必要的中间结果生成，降低单个节点的计算量，提升整体效率。在此基础上，该文对分布式环境下Top-k连接策略进行了进一步优化。在真实图数据上进行的实验测试表明：该文提出的算法能够有效解决分布式环境下Top-k子图匹配问题，具有很好的扩展性，而且使用优化连接策略的算法性能较基础算法的效率有明显的提升。
关键词： 图搜索 子图匹配 Top-k子图匹配 分布式
Distributed Top-k subgraph matching
LAN Chao, ZHANG Yong, XING Chunxiao
National Laboratory for Information Science and Technology, Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China
Abstract:Top-k subgraph matching is a key operation in graph queries which is widely used in all kinds of applications such as social networks and knowledge graphs. Top-k subgraph matching is more challenging in distributed environments since it involves data and task transfers. Thus, existing local Top-k subgraph matching methods do not work well in distributed environments. An algorithm was developed to address this issue by dividing the problem into query decomposition, query execution, and ranked join stages. The query decomposition avoids unnecessary data transfers during the querying stage. The ranked join technique avoids generating unnecessary temporal results that reduces the overall latency of the algorithm. The algorithm effectiveness and efficiency were tested using real data and the results indicate that the algorithm, especially the optimized version, effectively solves the distributed Top-k subgraph matching problem.
Key words: graph searchsubgraph matchingTop-k subgraph matchingdistributed systems
Top-k子图匹配被广泛应用到社交网络[1]、知识图谱[2, 3]等多个领域。在类似应用场景中，图数据的边和点数通常都在百万级以上，而且边和点上都包括丰富的信息，数据量庞大，因此类似规模图数据通常被部署在分布式环境中管理。分布式Top-k子图匹配问题便是研究如何在分布式管理的图数据上做快速的Top-k子图匹配检索。分布式环境下图被划分到多个分区中，每个分区只包含部分原始图数据，因此直接采用传统针对单机环境的Top-k子图匹配方法检索每个完整匹配结果可能需要同时访问多个分区的数据。在查询频度高的应用场景中，这种方法可能会导致大量分区间的数据传输[3, 4]。
为了避免查询时频繁的数据传输，本文采用“分治”的思想，先将原查询图进行划分，分别进行检索，再汇总查询结果。对查询做划分的好处是在每个查询执行时无须同时访问多个分区数据，只需要在相应的图分区执行相应的查询，最终将子查询结果按照公共节点连接成完整结果，再按照评价函数F排序产生Top-k。但该方法在实际应用场景下同样存在问题：1) 图可能会很大，枚举所有中间结果并且排序的代价很高； 2) Top-k结果产出并不需要所有中间结果，全部产生会造成不必要的开销。因此，采用“分治”法进行分布式环境下Top-k子图匹配还需针对上述2个问题进行优化，具体来讲有3个关键问题需要解决：1) 如何划分并执行子查询，产生中间结果支持后续的Top-k连接操作； 2) 如何避免产生全部中间结果； 3) 如何最小化产生中间结果的数量。
本文提出了一种新的针对分布式图数据的Top-k子图匹配算法：首先，形式化定义了分布式Top-k子图匹配的问题，提出包括拆分子查询—执行子查询—连接结果3个步骤的算法； 其次，提出了一种针对分布式图查询的灵活的评价函数体系，能够在查询运行时动态调整子查询的排序策略，实现更高效的Top-k连接； 再次，基于上述的评价函数体系，进一步探讨了针对分布式环境中影响算法效率的因素并且提出了优化策略； 最后，通过实验验证算法的有效性。
1 问题定义1) 图
图G: (V,E,L)包含点的集合V和边的集合E，每个点v∈V(或边e∈E)有描述L(v)(或L(e))，包含当前节点(或者边)的信息。点表示实体，边表示2个实体间的关系。
2) 查询
查询Q: (VQ,EQ)也是1个图。每个查询顶点表示对1个实体的描述，连接2个查询顶点的边表示顶点之间的关系或者约束。
3) 匹配子图
给定图G: (V,E,L)和查询Q: (VQ,EQ)。在G中Q的匹配子图(下文也称匹配结果或匹配)φ(Q)被定义为G中满足映射函数φ的子图。φ将Q中的点u映射到G中的点φ(u)，将Q中的边e=(u,v)映射到G中的边φ(e)=(φ(u),φ(v))。
4) 评价函数
定义FV(或FE)为查询点(或边)和其在图G中的匹配点(或边)的相似性函数。给定查询Q和其匹配φ(Q)，一般性的评价函数F(φ(Q))被定义为
| $F\left( \phi \left( Q \right) \right)=\sum\limits_{v\in {{V}_{Q}}}{{{F}_{V}}}\left( v,\phi \left( v \right) \right)+\sum\limits_{v\in {{E}_{Q}}}{{{F}_{E}}}\in {{F}_{E}}\left( e,\phi \left( e \right) \right).$ | (1) |
5) Top-k子图匹配
给定查询Q、图G、评价函数F，Top-k子图匹配目标是找到大小为k的匹配集Q(G,k)，并且满足对任何φ(Q)Q(G,k)，存在φ(Q)′∈Q(G,k)，使得F(φ(Q)′)≥F(φ(Q))。
6) 分布式Top-k子图匹配
给定图G，划分函数ψ将G划分为若干分区。 ψ(G)=(G1,G2,…,Gn)。 分布式Top-k子图匹配的目标是从ψ(G)上找到查询Q在图G上的Top-k匹配Q(G,k)。 关于图划分的相关工作如文[5-8]，划分方法主要有边分区[5, 6]和点分区[7]等。本文假设图采用点分区的方式，且支持分区存在副本的情况。
图 1是分布式子图匹配的示例。查询图Q由3个标签分别为A、B、C的顶点以及3条边(A，B)、(B，C)和(A，C)组成。目标数据图G包含许多能够匹配标签A、B、C的点和连接不同点的边。给定自定义的评价函数F，查询目标是从G中找到满足Q的且得分为Top-1的匹配子图。每个匹配子图都包含3个顶点，分别匹配标签A、B、C，并且3个点之间存在相连的边，例如(a1b1c1)和(a1b1c2)。 假设图G划分为2个分区G1和G2。 G1包含所有A标签的点和A与其他点的连接信息，G2分区包含了B、C标签的点及B、C与其他点的连接信息。在这种划分模式下，如果直接在2个分区上分别执行Q，因为G1分区缺少B和C之间的连接信息，所以在G1分区执行查询时需要同时访问G2分区中B、C相关的数据，可能会导致大量数据传输开销。
-56-8-871-1.jpg "点击查看原图") |
| 图 1 分布式Top-k子图匹配查询示例 |
| 图选项 |
2 分布式Top-k子图匹配分布式Top-k子图匹配算法步骤包括：1) 将原始查询划分为多个子查询； 2) 在分布式图上并发执行各个子查询，获得子查询的结果； 3) 连接子查询的结果，生成最终的Top-k结果。
2.1 子查询划分子查询划分的原则是避免划分产生的子查询在执行过程进行跨分区数据访问。本文将图查询统一划分为2层树结构，每个查询图包含1个根节点和1层叶子节点。以图 1所示查询为例，采用和划分图G相同的规则将Q划分为子查询Q1和Q2，如图 2所示。令Q1包括标签A、B、C和边(A，B)、(A，C)。 Q2包括标签B、C和边(B，C)，然后在各个分区上分别执行Q1和Q2，得到Q1和Q2的匹配结果。
-56-8-871-2.jpg "点击查看原图") |
| 图 2 查询划分示例 |
| 图选项 |
算法采用2层树结构(以下简称星形划分)作为基本查询单位，对于任意拓扑形状的图查询Q，都先将Q进行若干星形划分，再分别执行。 采用星形划分的原因是其具有如下优势。
1) 在点划分模式下，星形划分的匹配检索可以在点分区模式图的各个分区内独立执行，无须在多个分区之间交换数据。假设Qi是Q的星形划分，且vj∈V是Qi根节点的匹配点。则在点分区模式下，图G一定存在分区Gj，包含vj和vj所有邻接点和边的信息，即vj为根节点的所有子图匹配都被包含在Gj中，因此Qi在G中的每个匹配子图都至少被完整包含在G的某个分区里。
2) 星形划分的匹配算法较一般图的匹配算法复杂度低。例如子图同构是NP完全问题[9]，不存在多项式时间复杂度的精确算法，一般的解决方法是采用启发式方法或者构建索引加速[10, 11]。而针对树形结构的Top-k子图匹配有多项式时间的算法[12]，且结果为精确解。综上所述，在分布式环境下，星形划分无论从算法角度还是实现角度都具有优势。
2.2 子查询执行子查询执行算法的输入是查询Q的星形划分Qj∈(Q1,Q2,…,Qm)和图ψ(G)=(G1,G2,…,Gn)； 输出是Qj的Top-k匹配子图。
对每个图分区Gi∈(G1,G2,…,Gn)，执行如下步骤。
步骤 1 初始化结果集Ri与优先队列Pi为空。
步骤2 以每个点v∈Gi为根节点产生与Qj匹配得分最高的子图，添加到Pi中。
步骤 3 将Pi中得分最高的匹配子图S取出，放入Ri中，并且将和S有相同根节点且得分仅次于S的匹配子图加入到Pi中。
步骤4 如果Ri<k，且Pi≠0，则继续执行步骤3，否则跳转到步骤5。
步骤5 返回结果集Ri。
当所有图分区都返回Ri后，汇总并取得分最高的k个结果作为Qj的Top-k的子图匹配。
上述算法的核心操作是步骤2产生以图分区中每个节点v为根节点的Qj的匹配子图。图 3是这一过程的示例，图 3中根节点是X的匹配点x1，得分为0.5。X的邻接点中Y、Z的匹配点各有3个。算法首次执行步骤2时，先将各个节点的匹配点按照得分逆序排列，然后取由根节点匹配点x1和Y、Z的匹配点中得分最高的点组成子图，即(x1(0.5),y1(0.6),z1(0.9))。 此后如果在步骤3中，该子图被从Pi中选出放入Ri中，便可直接通过已有Y、Z结果列表产生得分次高的子图，即(x1(0.5),y2(0.5),z1(0.9))。 在实现该步骤时，可以为每个根节点的匹配点维护s个有序列表，s表示除根节点外Qj的节点个数，用于快速查找以当前点为根节点的下一个最优子图匹配。对于Top-k检索而言，Top-1结果包含s个有序列表中的s个候选节点，Top-k的结果只需额外增加k-1个候选节点即可产生，因此维护s+k-1个候选节点即可产生以当前节点为根节点的Top-k匹配子图。
-56-8-871-3.jpg "点击查看原图") |
| 图 3 最优匹配示例 |
| 图选项 |
步骤2的时间复杂度最差情况为 O(|V||VQ|+|E||EQ|)。 假设图G中节点的最大度数为d，则步骤3和4的时间复杂度为O(m|VQ|+(k+|VQ|)ln k)。 在实际情况中|VQ|、k、m往往远小于V和E，算法时间复杂度主要由图G的点和边数决定。
2.3 子查询结果连接子查询结果连接是算法的最后一步，目标是连接子查询的结果形成最终Top-k匹配子图。如图 4所示，查询Q(A,B,C)在算法中首先被划分为Q1(A,B)和Q2(B,C)，划分点为B，在分布式图上执行Q1和Q2，得到如图 4所示的结果。此后将Q1和Q2的匹配结果中B的匹配点相同的结果连接起来，得到最终Q的查询结果。例如查询Q的Top-1结果为(a2b1c2)，得分为2.7。
-56-8-871-4.jpg "点击查看原图") |
| 图 4 子查询连接示例 |
| 图选项 |
通过图 4的示例可以看出，连接包括2个基本过程：连接子查询的匹配结果和选取Top-k匹配。连接操作是数据库查询的1个基本操作，本文采用关系型数据库中的常用的哈希连接(Hash join)，划分自同一查询Q的不同子查询Qi和Qj的匹配子图能够连接当且仅当这2个子图的查询公共点的匹配点相同。Top-k子图匹配的基本过程如下。
步骤1 初始化结果集R为空。对星形划分查询集Qj∈(Q1,Q2,…,Qm)，执行每个Qj，获取Top-k′个子查询结果。其中k′是系统参数，初始可以设k′=k。
步骤2 对m个子查询的匹配列表进行连接，并且保存其中得分最高的k个结果到R中。记R中最低分匹配的得分为θ。 θ为当前Top-k匹配得分的下界。
步骤3 对每个子查询Qj，维护Top-k匹配的得分的上界θj。 当θj>θ时，说明来自当前子查询的匹配子图仍有可能通过和其他子查询的匹配子图连接产生目前比R中结果得分更高的结果，因此继续取k′个Qj的匹配子图，并和其他子查询的匹配子图进行连接，然后更新R、θ和θj。 否则当前子查询停止更新。
步骤4 如果所有子查询Qj∈(Q1,Q2,…,Qm)停止更新，则返回R为最终结果。否则继续步骤3。
步骤3中上界θj计算采用类似文[13]提出的针对关系型数据有序连接的上界模式，该上界的定义如下：给定n个查询(Q1,Q2,…,Qn)的匹配列表(L1,L2,…,Ln)，列表中的每个匹配按照评价函数F定义的分数逆序排列。令ti,j为Li的第j个匹配，假设当前Li的长度是m，则Li的上界定义为
| ${{\theta }_{i}}=F({{t}_{i,m}})+\sum\limits_{j=1,j\ne i}^{n}{F({{t}_{j,1}})}.$ | (2) |
2.4 优化的Top-k子图匹配算法尽管节2.3提出的子图匹配算法可以返回Top-k精确匹配结果，但是分布式Top-k子图匹配与文[13]的关系型数据有序连接的应用场景有很大区别。文[13]中的方法针对单机关系型表数据，表中包含所有待连接的数据项，而分布式子图匹配的待连接数据是随着算法执行在分布式环境中动态产生，区别主要体现在如下方面。
1) 分布式环境下和单机环境相比，存在计算节点之间的数据传输和任务调度开销，算法应该尽量减少数据传输的量和频次。例如在步骤3中，每取k′个Qj的子图匹配，都需要在每个分区上进行任务调度和数据传输，因此步骤3中的相关操作需要针对分布式环境进行优化，以降低数据传输和任务调度引起的额外开销。
2) 子查询的匹配列表是步骤3通过子查询执行算法动态产生的，并非静态数据。如节2.2介绍，子查询执行算法的时间和空间复杂度以及分布式环境下数据传输量的大小都和产生匹配总数直接相关，而步骤3中子查询需要产出的匹配总数只由上下界条件决定，因此上下界选取是否合理会直接影响算法效率。
3) 当前按照式(2)计算出来的上界是十分松弛的。在计算上界θj时，参与计算分数的不同匹配列表中的结果会包含相同的连接点，而连接点的分数在上界中会被重复计算。例如在图 4中计算Q1上界时，假设当前访问到(a4b4)，则上界θ1为(a4b4)：1.5和Q2最高分数(c2b1)：1.8之和3.3。B的匹配点b1和b4的分数都被计算到θ1中，θ1包含4个点的分数，但是下界θ的计算只会包含3个点的分数。因此目前的定界模式十分松弛，需要做进一步优化。
针对上述不同，本文提出改进的Top-k子图匹配算法。优化的基本思想是在执行子查询时，将连接点的分数按一定的比例拆分到包含该连接点的不同子查询的匹配中，以避免计算上界时连接点重复计算问题。给定查询Q1和Q2，令J为Q1和Q2的公共点集，令Q*1(Q*2)为Q1(Q2)中除J以外的部分，给定参数ω，定义新的评价函数
| $F\prime (\phi \left( {{Q}_{1}} \right)=\omega F\left( \phi \left( {{Q}^{*}}_{1} \right) \right)+\omega F\left( \phi \left( J \right) \right),F\prime (\phi ({{Q}_{2}})=F(\phi ({{Q}^{*}}_{2}))+\left( 1\omega \right)F\left( \phi \left( J \right) \right).\text{ }$ | (3) |
证明：首先证明采用F′ 作为评价函数的正确性。因为θ的计算不变，所以只需分析θj的正确性。构造点集J′和J″，令F(φ(J′))=ωF(φ(J))、F(φ(J″))=(1－ω)F(φ(J))，有F′(φ(Q1))=F(φ(Q*1)+φ(J′))、F′(φ(Q2))=F(φ(Q*2)+φ(J″))。 因此使用F′ 可以等价转换为使用F的情况，命题得证。
其次证明采用F′ 作为评价函数的上下界比采用F更紧凑。假设当前子查询为Q1和Q2，假设采用F算法停止时下界为θ，Q1(Q2)共查询了l(r)个匹配，即Q1的上界θ1=F(t1,l)+F(t2,1)，且θ1≤θ。 因下界相同，所以采用F′ 算法停止时下界同样为θ。 令t′i,j为Qi的第j个匹配，假设Q1查询了l个匹配，则此时Q1的上界θ′1=F′(t′1,l)+F′(t′2,1)，由F′ 的定义可知，F′(t′1,l)≤F(t1,l)、F′(t′2,1)≤F(t2,1)，因此θ′1≤θ1，同理通过对称性可知θ′2≤θ2，命题得证。
图 5是采用F′ 作为评价函数的子图匹配和连接过程示例。与图 4示例类似，查询Q(A,B,C)被划分为Q1(A,B)和Q2(B,C)，划分点为B，查询目标为Q的Top-1结果。首先在分布式图上分别执行Q1和Q2，得到如图 5(a)中所示匹配点集； 然后用F′ 对子匹配结果进行排序，生成匹配结果的降序列表。图 5(b)和(c)分别是F′ 中ω=0.5和ω=0.1时的连接过程，并且可以看出当ω选取不同值的时候，连接算法的实际开销并不相同。当ω=0.5 时，如图 5(b)所示，从每个列表中各取2个匹配做连接后，列表的上界已经小于当前下界，可以确定Top-1的结果就是(a2b1c2)。 而当ω=0.1时，如图 5(c)所示，需要分别从每个列表里取3个和4个匹配后才能判断(a2b1c2)是Top-1结果，可见ω会直接影响连接算法开销。
-56-8-871-5.jpg "点击查看原图") |
| 图 5 采用优化评价函数的子图匹配连接 |
| 图选项 |
但如何选择最优的参数ω并不直观。针对特定数据集上特定工作流选择最优的ω需要考虑查询本身、目标数据特征、评价函数性质和分布等诸多因素，因此在没有执行查询前确定最优ω十分困难。对于实际应用来说，可以采用启发式的方法选择ω。 由于最终算法的开销取决于从Q1和Q2访问的结果数目之和，且选择不同的ω不会影响算法停止时的下界，只会影响上界。下界相同的情况下，当前查询Qi的上界越大，需要从Qi访问的对象就越多。令ω=0，则F′(φ(Q2))=F(φ(Q*2))+F(φ(J))，此时Q2的Top-1结果得分最大，因此Q1的上界最大，算法结束时从Q1访问的对象越多。同理当ω=1时，Q2的上界最大，算法结束时从Q2访问的对象越多。因此，在Q1和Q2查询结构比较均匀的情况下，可以取ω=0.5，此时Q1和Q2上界取值均衡，从2个查询中访问的对象总数可能较低。
除了上界松弛的问题外，分布式环境下数据传输的额外开销是算法另一个主要的性能瓶颈。本文可以通过改进算法来降低数据传输的频度，进而降低整体的算法开销。综上所述，优化的Top-k子图匹配算法如下。
步骤1 初始化结果集R为空，对星形划分查询集Qj∈(Q1,Q2,…,Qm)，执行每个Qj，获取Top-k′ 的子查询结果。其中k′是系统参数，初始可以设k′=k。
步骤2 对m个子查询的匹配列表进行连接，并且保存连接结果到R中。
步骤3 如果|R|<k，则继续从每个查询Qj取k′ 个匹配，和其他子查询的匹配列表进行连接，然后更新R，记R中得分第k高的匹配得分为θ。 如果|R|≥k，执行步骤4。
步骤4 对每个查询Qj，计算通过连接可以获得Top-k匹配的最低得分θ′j，并计算所有得分大于θ′j子图匹配，和其他子查询的结果集进行连接，然后更新R。
步骤5 返回R中得分最高的k个匹配作为最终Top-k结果。
其中，步骤4中的最低得分计算公式如下：
| $\theta {{'}_{j}}=\theta -\sum\limits_{j=1,j\ne i}^{n}{F({{t}_{j,1}})}$ | (4) |
证明：将θ′j带入式(2)中替换等号右边第一项，可得θ′j=θ，根据节2.3的算法，当前子查询的停止条件已经满足，证明式(4)正确。
3 实验与结果分析实验采用DBPedia[14]数据作为测试数据集。DBPedia是一个复杂的知识图谱数据集，图中的节点表示真实世界中的实体，边表示2个实体之间的关系。实验使用数据的相关统计见表 1。 查询测试集采用文[3]使用的模板生成方法随机产生2 000个图查询，均为可以拆分成2个星形查询的随机形状，节点数为3~5。
表 1 DBPedia数据统计
| 点数 | 边数 | 点种类数 | 关系种类数 | 大小 |
| 420万 | 13 300万 | 359 | 800 | 40 GB |
表选项
分布式实验环境基于Apache Spark搭建，采用1台master，4台slave的架构，每个计算节点有4个CPU 核，30 GB内存。服务器运行Ubuntu 14.04系统，Hadoop 2.6，Spark 1.5。图数据以HDFS文件形式存储，通过Spark管理图的分布式划分和加载。算法均基于Spark计算框架使用Scala2.10实现。
实验测试了基础Top-k子图匹配算法和优化算法，从划分为8个分区的DBPedia数据中查找 2 000 个图查询的Top-20、Top-50、Top-100和Top-200的匹配，通过算法停止时2 000个查询的平均连接的匹配总数和算法执行时间2个维度比较2个算法的时间和空间消耗。此外还测试了分别将图划分为2、4、8、16个分区时查询Top-20算法的时间消耗，实验结果如图 6所示。结果表明本文的基础匹配算法和优化算法都能有效解决分布式环境下的Top-k子图匹配问题。从图 6a的结果来看，优化算法在算法停止时连接的子匹配图数量少于基础算法，证明了优化算法在连接时使用的上界计算策略优于普通算法，避免产生很多不必要的中间结果，节省了计算资源。从图 6b的结果来看，优化算法的时间性能比基础算法平均提升30%~40%，证明更准确的上界计算策略和针对分布式环境改进的连接策略对算法性能的提升有很大帮助。综上所述，优化算法在空间复杂性和时间复杂性方面都明显优于基础算法。
-56-8-871-6.jpg "点击查看原图") |
| 图 6 实验结果对比 |
| 图选项 |
从图 6c的结果来看，本文提出的2个算法具有良好的扩展性，特别是在节点数比较低的时候，增加并行节点数对算法的整体性能的提升效果明显。实验结果同时表明，随着节点数的提升，分布式环境的额外开销，如节点间数据传输和任务调度逐渐形成瓶颈，从而影响了算法的扩展性(例如从8个分区增加至16个分区的情况)。这也反映了降低分布式环境下因数据传输导致额外开销工作的必要性。
4 结 论本文系统地分析并形式化定义了分布式环境下的Top-k子图匹配问题，并与传统数据库的排序连接问题进行对比，指出了已有方法解决分布式环境下Top-k子图匹配问题的局限性，分析了可以改进的方向，并提出了包括拆分查询—执行子查询—连接结果3个步骤的算法，有效地解决了分布式环境下的Top-k子图匹配问题。本文通过进一步分析算法的数据传输过程，提出了针对分布式环境的优化策略，降低了算法执行过程中数据的传输频次，从而降低了分布式环境下数据传输的开销。最后通过基于真实图数据的实验验证了算法的有效性。
参考文献
| [1] | Journal of Central South University(Science and Technology), 41(2):649-654.--> ?Gupta M,Gao J,Yan X,et al.Top-k interesting subgraph discovery in information networks[C]//ICDE2014.Chicago,IL,USA:IEEE,2014:820-831. |
| [2] | Journal of Central South University(Science and Technology), 41(2):649-654.-->Huang J, Abadi D J, Ren K. Scalable SPARQL querying of large RDF graphs[J]. Proc VLDB Endow, 2011, 4(11) : 1123–1134. |
| [3] | Journal of Central South University(Science and Technology), 41(2):649-654.-->Yang S, Wu Y, Sun H, et al. Schemaless and structureless graph querying[J]. Proc VLDB Endow, 2014, 7(7) : 565–576.DOI:10.14778/2732286 |
| [4] | Journal of Central South University(Science and Technology), 41(2):649-654.-->Khan A, Wu Y, Aggarwal C C, et al. NeMa:Fast graph search with label similarity[J]. Proc VLDB Endow, 2013, 6(3) : 181–192.DOI:10.14778/2535569 |
| [5] | Journal of Central South University(Science and Technology), 41(2):649-654.--> Gonzalez J E,Low Y,Gu H,et al.PowerGraph:Distributed graph-parallel computation on natural graphs[C]//USENIX 2012.Hollywood,CA,USA:USENIX Association,2012:17-30. http://cn.bing.com/academic/profile?id=2118239891&encoded=0&v=paper_preview&mkt=zh-cn |
| [6] | Journal of Central South University(Science and Technology), 41(2):649-654.-->Albert R, Jeong H, Barabási A. Error and attack tolerance of complex networks[J]. Nature, 2000, 406(6794) : 378–382.DOI:10.1038/35019019 |
| [7] | Journal of Central South University(Science and Technology), 41(2):649-654.--> Abou-Rjeili A,Karypis G.Multilevel algorithms for partitioning power-law graphs[C]//Proceedings of the 20th International Conference on Parallel and Distributed Processing.Rhodes Island,Greece:IEEE Computer Society,2006:124-124. http://cn.bing.com/academic/profile?id=2153752762&encoded=0&v=paper_preview&mkt=zh-cn |
| [8] | Journal of Central South University(Science and Technology), 41(2):649-654.--> Xin R S,Gonzalez J E,Franklin M J,et al.GraphX:A resilient distributed graph system on spark[C]//First International Workshop on Graph Data Management Experiences and Systems.New York,USA:ACM,2013:1-6. http://cn.bing.com/academic/profile?id=1982003698&encoded=0&v=paper_preview&mkt=zh-cn |
| [9] | Journal of Central South University(Science and Technology), 41(2):649-654.-->Ullmann J R. An algorithm for subgraph isomorphism[J]. J ACM, 1976, 23(1) : 31–42.DOI:10.1145/321921.321925 |
| [10] | Journal of Central South University(Science and Technology), 41(2):649-654.--> He H,Wang H,Yang J,et al.BLINKS:Ranked keyword searches on graphs[C]//SIGMOD2007.New York,USA:ACM,2007:305-316. |
| [11] | Journal of Central South University(Science and Technology), 41(2):649-654.-->Sun Z, Wang H, Wang H, et al. Efficient subgraph matching on billion node graphs[J]. Proc VLDB Endow, 2012, 5(9) : 788–799.DOI:10.14778/2311906 |
| [12] | Journal of Central South University(Science and Technology), 41(2):649-654.--> Gou G,Chirkova R.Efficient algorithms for exact ranked twig-pattern matching over graphs[C]//SIGMOD2008.New York,USA:ACM,2008:581-594. http://cn.bing.com/academic/profile?id=2105247179&encoded=0&v=paper_preview&mkt=zh-cn |
| [13] | Journal of Central South University(Science and Technology), 41(2):649-654.-->Ilyas I F, Beskales G, Soliman M A. A survey of top-k query processing techniques in relational database systems[J]. ACM Comput Surv, 2008, 40(4) : 1–58. |
| [14] | Journal of Central South University(Science and Technology), 41(2):649-654.--> Dbpedia.Dbpedia[Z/OL].(2015-01-01).http://wiki.dbpedia.org/. http://cn.bing.com/academic/profile?id=2215376118&encoded=0&v=paper_preview&mkt=zh-cn |
