迟贺宇，秦小麟，李 瑭，费 珂

(南京航空航天大学 计算机科学与技术学院，南京 211106)

1 引 言

在计算机领域，图查询算法是图论算法的重要组成部分，如今各种应用程序领域都存在大规模图形数据，如何对它们进行高效的查询，是一个巨大的挑战，并且具有重要的价值和意义.

由于第二代互联网的兴起，特别是超大规模和高并发的社交网络服务(Social Networking Services，SNS)类型的纯动态网站的出现，诞生了非关系型数据库(Not only Structured Query Language，NoSQL)，其中图数据库(Graph Database)支持将数据的实体抽象为顶点，实体之间的关系抽象为边，将数据以图的形式进行存储.对图数据的操作不仅涉及数据顶点自身的信息，而且涉及数据顶点之间的结构关系.可以将对图数据的操作抽象为获取特定顶点、获取特定路径、获取特定子图等，通过实现这些通用操作，实现图数据的相关应用.

根据2021年最新相关数据，新浪微博的注册人数已经超过5.23亿，因此新浪微博的社交图有超过5.23亿个顶点，若以关注关系作为边进行存储，大约会有500亿条边.而如此大规模的数据，随着新用户的增加，关系的建立与解除、图结构变换等现象时有发生.另一方面第五代通信技术与全球定位系统飞速发展，私家车数量增多，使得人们在出行前或在出行时习惯进行路线规划.以私家车为顶点，道路为边的交通网络中，往往需要发现两点间满足不同标准的路径，如红绿灯最少的道路、同行车辆最少的道路，用来使客户规划自己的行程.由实际数据抽象成的结构复杂的大图数据和实际问题衍生出的图查询问题，为图的可达性查询算法带来了挑战，也一直是图论算法中的研究热点.

此外，随着硬件技术的发展，高性能的CPU已经降低了由图大小和其复杂性导致的计算时间消耗，整个计算机行业正在向并行计算过渡[1].高度并行的多核系统为新型高效、可扩展的图处理算法提供了机会.

目前，许多关于图数据传统串行可达性查询算法的技术和相关应用被提出[2-6].图数据的可达性查询方法有很多种，其核心思想是创建一个索引结构辅助查询，从而缩短查询的时间，按照类别可以划分为以下3种[4]：1)基于减枝的深度优先搜索法(Pruned Depth-first Search)[7-13]，用减枝法优化传统深度优先搜索算法进行查询；2)传递闭包法(Transitive Closure Retrieval)[14-18]，计算所有顶点的传递闭包并回答查询；3)标签匹配法(2-Hop Label Matching)[19-21]，根据索引结构中的标签信息进行查询.

虽然目前存在着许多对图可达性查询的高效算法，但是它们也存在各种各样的问题.对大图查询算法而言，问题的关键是对空间消耗和时间消耗的平衡，在预处理阶段进行大量的准备工作，生成庞大的索引会导致大量的空间消耗，但是这会为查询工作带来极大的便利.上述第二类传递闭包法，在预处理阶段将所有顶点的传递闭包存储下来，极大的提高了单次查询应答的效率，但是这造成了大量的空间浪费.如果生成较为简单的索引，虽然会减少空间消耗，但是在查询过程中会产生过多的时间浪费.随着多核服务器的出现，这些串行的算法无法更好的利用硬件发展带来的计算优势，造成了极大的资源浪费.目前，有许多对并行深度优先搜索算法的技术和研究成果[22-24]，但是这些研究工作只针对某种算法，单一的追寻算法效率，没有结合适当的索引去解决实际的问题，无法保证算法对不同索引结构的适用性，即无法解决需要索引的结构复杂的网图上的查询问题.

在图的可达性查询算法中，构建一个能够平衡空间消耗和查询效率的索引结构是一个有挑战性的问题，且现有工作的索引与算法不适用于并行系统，因此本文提出了一种2-lists索引.该索引由顶点表和边表组成，顶点表存储顶点和边的信息，考虑到线性表线性查找的局限性，加入了边表进行辅助查询使其做到随机访问的同时，还可以进行反向查询，占用的内存空间和构建该索引需要的时间均是随图数据规模的变化而线性变化.基于该种索引提出了一种并行化深度优先搜索算法，2-lists-PDFS算法，该算法高效且具有通用性，充分的利用多核服务器的硬件优势.将双表索引和并行化算法结合，提升了针对复杂图数据查询的效率.最后在斯坦福大学SNAP实验室收集的真实公开数据集进行了大量的实验.

本文第2节介绍现有图可达性查询算法和并行图搜索算法的一些相关工作；第3节对2-lists索引结构和2-lists-PDFS算法进行详细的介绍；第4节详细介绍索引结构与算法实验的结果，并进行分析；在文章最后，总结全文，并提出下一步的工作方向.

2 相关工作

随着社交网络分析、Web语义分析、生物信息网络分析以及交通导航等新兴应用的快速增长，不同领域出现了规模庞大、内部结构复杂、查询需求多样的大图数据，同时带来了许多图查询算法的相关应用，如道路网中的路线规划[7]、社交网上的好友推荐[8]、时空轨迹数据的可达区域预测[9]，如何对这些数据进行高效且正确的查询，受到了学术界和工业界的广泛关注.

2.1 减枝优化法

此分类中的技术使用图上的深度优先搜索算法(Depth-First-Search，DFS)进行每个可达性查询，它们预先计算了图上的某些辅助信息以修剪搜索的空间，从而提高查询效率.Yildirim等人[10]提出了一个称为Grail的简单且可扩展的索引，该索引基于随机间隔的思想，可以有效的处理非常大的图形，索引构建时间和空间都是线性的，在回答图查询问题时，可以通过顶点的标签，对不可达的查询顶点进行快速消除，这也是此类算法中的代表性算法.Zhou等人[11]针对传统图查询算法无法放大到大图的问题，提出了一种自下而上的算法buTR，该算法删除图数据所有冗余边，以获得唯一的最小无向图，从而降低了时间消耗和空间消耗带来的成本.Xie等人[12]提出了一种复合型索引BFSI-B，它使用特殊索引来提升k-hop查询方法的修剪效率，从而降低可达性查询所需的时间.Du等人[13]提出了一种标记方案，有效地构建一个紧凑的索引来捕获顶点之间最短的距离，从而进一步增加顶点标签的覆盖范围，使得无需进行图遍历就可以回答许多查询.

上述方法在预处理计算和空间消耗方面开销较小，但是相应的查询效率不佳.本文提出的2-lists-PDFS算法可以归纳为此类，2-lists索引结构采用双链表索引结构，占用空间较小，相比于传统串行算法，使用并行计算的2-lists-PDFS解决了查询效率不佳这一问题.

2.2 传递闭包法

顶点的传递闭包是图中该顶点可达顶点的集合.此类算法通过一些手段，来加快计算传递闭包的效率.Schaik等人[16]提出了PWAH方案，使用压缩位向量来紧凑地表示传递闭包，降低存储传递闭包所需的空间.Chen等人[17，18]提出了两种新的图分解方法，分别将图分解成最小的不相交链集和一系列可能具有相同边的生成树，将图上的传递闭包压缩到更小结构上的传递闭包，以提高查询效率和降低存储消耗.

给定一些顶点，上述方法只要查询指定顶点所存储的传递闭包，即可完成查询，但是由于派生和存储传递闭包中产生的大量预计算和空间开销，使得它们无法适用于大图数据.基于并行计算的2-lists-PDFS算法要比基于串行深度优先搜索算法求解传递闭包的算法有更高的查询效率，从而减少预计算开销.但存储传递闭包带来的空间消耗仍然没有得到有效的解决.

2.3 标记匹配法

此类算法将某些特定标记记录在索引结构中，通过标记信息，来回答图的可达性查询.这类方法以Cohen等人[19]提出的2-hop标记为代表，它将每个顶点所到其它顶点的最短距离或距离总和记录在索引结构中，并提出了一种有效的算法，用于查找某条指定路径.Bramandia等人[20]对2-hop标记法进行了更新，使得新方法可以适用于由图数据顶点的更新而产生的连通性变化.Jiang等人[21]提出了3-hop标记法，首先提取出诱导子图，基于上限密度启发式算法和早停跳选择策略，以较小的索引大小对剩余的传递信息进行编码，完成标记.

此类算法的主体思想是对顶点标签进行并集计算，当标签集较小时，此类算法有很高的查询效率.但是当标签集较大时，容易产生冗余的数据，从而导致查询效率降低.2-lists索引结构只存储边，不存距离、路径等附加信息，因此索引结构占用空间小，对图进行查询不会产生冗余操作.

2.4 并行图查询算法

目前，有许多并行深度优先搜索算法的相关工作.Acar等人[22]提出了一个用于表示深度优先搜索中顶点边界的新数据结构，每个线程根据当前数据结构是否为空和当前线程的工作状态利用线程通信技术来完成负载平衡，从而实现深度优先搜索算法的并行化.Aleksandrov等人[23]用图分割技术，为每个线程分配不同的图分区，在预处理阶段分别计算距离信息并存储，根据这些信息，在查询阶段在不同的线程上完成查询.Naumov等人[24]提出了一个基于路径比较与单源最短路径(Single Source Shortest Path，SSSP)的技术，将有向无环图压缩成有向树，然后对有向树使用并行化广度优先搜索，完成查询.但是这种方法，在GPU上更有效率.

上述方法全部采用邻接表，但是在实际应用中，往往需要功能性更强的索引结构，因此以上几种方法的应用不能够扩展到可达性查询等实际问题，2-lists-PDFS算法基于2-lists索引结构，可以有效地解决可达性查询等实际问题.同时上述工作将图按字典序并行化查询，但在可达性查询、图查询等问题中并非关键要素，2-lists-PDFS算法采用无序查询，从而加快可达查询的响应速度.

3 基于索引的并行图查询算法

为了便于说明问题，现定义如下符号：V={v1，v2，…，vm-1，vm}，为m个顶点的集合.E={ev1，v2，ev1，v3，…evm，vm-2，evm，vm-1}，为顶点之间的边组成的集合，其中evn，vm表示顶点vn有一条指向顶点vm的边.令G =(V，E)是一个顶点集为V，边集为E的有向图，用|V|来表示顶点集的大小，|E|来表示边集的大小.NL为索引结构中的顶点表，EL为索引结构中的边表.AD(v)为边表中每个顶点的数据块的地址的集合，共|V|个.P是线程的集合，M是缓冲区的集合.本文所使用的符号如表1所示.

定义1.对于属于顶点集V的任意两点vs和vt，如果存在一条定向路径以vs为起点vt为终点，那么可表示为vs可达vt(记作vs→vt).给定任意起始顶点vs和终止顶点vt，如果存在vs→vt，则返回True否则将返回False.如图1所示，存在一条有向路径使得va可达ve，记作va→ve.

图1 有向无环图

3.1 双表索引

索引对数据库具有十分重要的意义.如上文所述，在对大图数据进行查询时，应基于一个合适的索引，来平衡空间消耗和计算时间消耗.传递闭包法是将图内所有顶点的传递闭包均求解后将其存储，以便于进行查询访问时，能够有极快的响应时间.但是对于前文所述的社交网络图而言并不现实，因为这个方法造成的空间消耗是巨大的.

以前的工作在建立索引结构后，会对图进行预处理，并将一些辅助信息存放在索引中，但是在建立索引的过程中，会反复对图进行遍历，在大图数据中，图的复杂性随顶点数目的增多而增加，这意味着每一次对图进行遍历都将造成大量的时间浪费，而且存储过多辅助信息会造成极大的空间浪费.为了解决上述问题，本文提出了一个新的索引结构.

3.1.1 2-lists索引的基本结构

定义2.给定一个有向图G=(V，E)，对于该图构建2-lists索引结构，即顶点表NL和边表EL，二者均具有指针域，其中NL具有节点指针域，LN，EL具有正向指针域，Lfor和反向指针域，Lre.任意evi，vj∈E，EL(vj)∈LN(vi)，NL(vi)∈Lfor(vi)，NL(vi)∈Lre(vj).

图2是根据图1部分顶点构造的2-lists索引的基本结构，边表中的vc的反向指针指向顶点表中的a点，因为图1中存在一条边ea，c，vc的正向指针指向顶点表中的vc的数据块.这样做的好处是，在进行可达性查询中的祖先查询问题时，遍历反向指针可直接求得顶点的祖先.

在建立2-lists时，首先创建边表EL并将EL中每个顶点的地址记录在AD中，以便后续进行随机访问，如步骤3、步骤4.创建顶点表时，根据定义2，会将边表和顶点表对应的顶点连接起来，如步骤8～步骤11.

构建本索引结构的算法如下：

算法1.2-lists索引构建算法

输入：有向图G=(V，E)，顶点集V的大小|V|.

输出：2-lists索引表.

1.set AD←{}，NL←{}，EL←{}

2.foreach v in Vdo

3. add v into EL //构建边表

4. add &(EL(v))into AD //将边表中每个数据块的地址用顶点为关键字存放

5.endfor

6.foreach evi，vjin Edo

7.ifNL(vi)=0then//如果该顶点尚未被加入到顶点表中

8. add viinto NL //构建顶点表

9. NL(vi).Keypointer←AD(vj)//顶点表指针域指向边表对应数据块

10. EL(vi).Forpointer←NL(vi)//边表正向指针域指向顶点表对应数据块

11. EL(vj).Reporinter←NL(vi)//边表反向指针域指向起始顶点数据块

12.endif

13.endfor

根据算法1和图2进行相关说明.创建索引时，首先根据顶点数量建立边表，而后根据存在的边ea，c，建立顶点表，将va存入数据块中的数据域内，使用前面记录下的边表中vc数据块的地址ad(c)，将边表中vc数据块的地址记录在顶点表va数据块中的指针域中，而后将顶点表中va数据块的地址分别记录在边表va数据块的正向指针域和vc数据块的反向指针域中.值得一提的是，算法只给出了插入新顶点的伪代码，而对于已存在顶点，通过边表指针域中存放的地址，可以快速地定位到该顶点所在顶点表中的位置.

在使用2-lists索引进行图的搜索时，会先定位到某个顶点所在的顶点表数据块，然后根据该数据块指针域所存放的指针列表定位到边表中的相应数据块，再根据块中的正向指针，定位到顶点表，进行深度优先搜索.如果想要查询某个顶点的祖先，只需要从它的反向指针出发，进行搜索即可.如图2，遍历vc时，会先定位到vc所在的数据块，然后根据vc指针域的指针，分别指向了边表的ve和vf，再从他们的指针域出发，进行遍历，直到遍历完成.如果想要查询vc的祖先，只需要先定位到vc，然后遍历vc反向指针指向的顶点，即可查询出vc的所有祖先.

图2 2-lists索引结构图

3.1.2 2-lists索引大小及创建所需时间复杂度

上一节介绍2-lists索引结构以及构建索引的算法，本节将对索引的大小以及创建所需的时间复杂度进行分析.

对于一个有向无环图G=(V，E)，顶点集大小和边集大小分别表示为|V|和|E|，设边表的指针域大小为l，数据域大小为u.在构建边表时，还创建了存储边表中每个数据块地址的表AD，该表与|V|成正相关，假设每个数据块地址的大小为k，那么边表占用的总空间为:

S(EL)=(2l+u+k)×|V|

(1)

在创建顶点表时，顶点表每个数据块存储的数据域、指针域占用空间均与边表相同，但顶点表的指针域存放指针的数量是边集E的大小|E|，所以顶点表的大小为:

S(NL)=u×|V|+l×|E|

(2)

根据公式(1)和公式(2)，可以得出，2-lists索引总大小为:

S=(2l+2u+k)×|V|+l×|E|

(3)

根据公式(3)可以看出，2-lists的总大小随着|V|和|E|的大小而变化，即图数据顶点的数量和边的数量进行线性的变化.

对于第2步～第5步边表的建立，由于是顺序连续存储顶点信息，其所需时间只与顶点数有关，即时间复杂度为O(|V|)，对于第6步到第12步顶点表的建立，它会将图数据所有边的信息读取到内存中，逐条存储在顶点表中，而在确定某一个顶点对时，也可以根据存储边表数据块地址的AD集合来以O(1)的时间复杂度来查询每个顶点的位置，所以顶点表的建立所需时间与边数有关，即O(|E|)，所以2-lists索引结构所需的时间复杂度为O(|V|)+O(|E|)=O(|V|+|E|).

3.2 基于2-lists的并行化深度优先搜索算法

图的可达性查询可以用深度优先搜索算法来回答.并行化深度优先搜索算法(Parallel Depth First Search，PDFS)需要执行负载平衡以使所有线程繁忙，最简单的办法就是生成若干个线程，然后用负载均衡算法将数据分配给每个线程.

根据2-lists索引的特点，对一个顶点进行深度优先搜索时，从顶点表的指针域出发，对每个指针指向的顶点进行搜索，本文提出的2-lists-PDFS算法的基本思想在于，将顶点表的指针域中的每个指针指向的顶点，加载到不同的线程，分别进行深度优先搜索.负载平衡方法有很多，如工作窃取算法[25]，但是每个顶点所带来的工作量并不相同，产生工作量小的顶点会频繁的进行负载平衡，这会导致带来的收益会远小于负载平衡的消耗.因此，我们提出了一个负载平衡方法，使每个线程在工作状态和负载平衡阶段相互转化.

定义3.给定任意查询点vi，每个线程对应查询过程如下：

1)对所有vj满足evi，vj∈E，vj∈m.

2)对任意vk∈m，若vk没有被访问过，对所有vq满足evk，vq∈E，vq∈m，m为根据负载平衡指定的线程缓冲区.

3.2.1 并行化深度优先搜索算法

算法2. 2-lists-PDFS算法

输入：顶点集V，线程每次加载数据的数量T.

输出：遍历后的visit集合.

1.set visit←{}，K←{}，m←{}，p←{}，pm←{}

2.whiletruedo

3. p←m[1-T]//将缓冲区中的数据加载到线程中

4.foreach v in pdo

5.ifvisit[p.pointer]=falsethen

6. visit[p.pointer]=true

7. pm←p.pointer

8.ifpm.size=Tthen

9. writein(findmin(K)，pm)//将遍历得到的数据写入指定的线程中

10. K++

11.endif

12.endfor

13.endwhile

算法2表示了参与2-lists-PDFS算法的所有线程都需要执行的伪代码.每个线程维护自身的缓冲区m，从m中加载T个数据，如步骤3.在对顶点遍历时，根据访问数组visit判断顶点是否被访问过，未被访问的顶点使用原子操作将访问数组标记为已访问，如步骤5、步骤6，同时，将该顶点的子顶点加载至线程辅助缓冲区pm，然后根据负载平衡策略，将顶点按规则加载到缓冲区中，如步骤7～步骤9.

3.2.2 2-lists-PDFS的缓冲区

每个线程创建一个队列做缓冲区，队列的特点是先进先出(FIFO)，保证了先进入缓冲区的顶点优先进行遍历，防止造成因顶点积压，部分顶点长时间处于未被访问状态.为了减少访问冲突，每个线程除了进行读写时，不会占用任何缓冲区.在对当前数据块存储的顶点进行遍历时，缓冲区会存储该数据块指针域所指向的地址，也就是边表的数据块的地址，边表数据块中存储的数据域是当前被遍历顶点的子节点.

当线程开始工作时，会从缓冲区中读取并删除一些顶点，对其进行访问.删除的顶点数量由T决定，T表示每个线程每轮应遍历的顶点数目.T越大，线程每轮读的数据越多，每个线程每轮做的工作也就越多，从而减缓从缓冲区读数据的频率；T越小，每轮线程读的数据越少，每个线程工作越少，从而加快从缓冲区读数据的频率.同时，T还决定了辅助缓冲区pm一次性根据负载均衡策略向其他线程缓冲区写入数据的数量.

在线程工作时，记录下每个线程的工作量，记作K.K值越大，则代表该线程在单次查询工作中所做的工作越多，在负载均衡时，该线程被分配数据的优先级更低.K值同时也是评价负载平衡工作效果的标准，如果所有线程的K值相近，则说明负载均衡算法的效果良好.如果K值相差悬殊，说明算法负载均衡并没有有效的执行.值得一提的是，在进行图遍历的过程中，一定会遍历到已经遍历过的顶点，这些顶点作为已经实现的工作，属于无效工作量，也应该计入K值，从另一角度上看，无效工作相当于数据块的指针域内没有指针，只是工作量为1的正常顶点.所以，K值与线程每次从缓冲区读取的顶点数量T值成正相关.

3.2.3 2-lists-PDFS的负载平衡

上文提到，2-lists-PDFS算法是将当前访问节点的指针域中的指针加载到不同的线程中，在进行这个工作时，需要按照负载平衡策略将顶点加载特定的缓冲区中，平衡每个线程处理顶点的数量，使每个线程都处于工作状态.每次在将节点写入缓冲区前进行扫描，选出工作量最小的线程，即K值最小的线程，后再将节点加载到对应线程的缓冲区中.如图3所示，线程p3正在加载缓冲区m3的数据，而p1此时要将自己的数据写入到缓冲区，m2的K值为4，代表了对应线程工作量为4，是3个线程中工作量最少的线程，所以p1会将数据写入到m2当中.

图3 负载平衡示意图

需要注意的是，为了防止脏数据的产生，对缓冲区应进行存储访问控制.在将数据写入缓冲区时，如果发现相应缓冲区正处于使用状态，可能对应两种情况：1)有另一个线程正在向该缓冲区写入数据；2)有线程正从该缓冲区加载数据，准备进行它的工作.以上两种情况的发生会使准备进行写操作的线程进入等待状态，这会造成该线程无法进行数据的写入，造成长时间的等待状态.而为了应对这一种情况，线程应将准备写入的数据写入到按K值降序排列的另一线程的缓冲区中.如图4所示，线程p1正在向缓冲区m2中写入数据，此时，线程p3也需要向缓冲区写入数据，K值最小的是缓冲区m2，而这时，m2处于无法访问状态，所以p3需要向k值第2小的m1缓冲区写入数据，此时，m1处于可访问状态，数据顺利写入.

图4 访问控制示意图

4 实验与分析

4.1 实验设置

4.1.1 数据集与实验环境

为了验证本文提出的索引及相关算法的有效性与实用性，采用斯坦福网络分析平台实验室SNAP公开的数据集进行测试.自2004年起，SNAP实验室在分析大型社会网络和信息网络方面的研究蓬勃发展，到目前为止，该网站的最大图是具有2.4亿节点和13亿条边的Microsoft Instant Messenger网络.本文所使用的是如下5组公开数据集，如表2所示.

表2 数据集说明

1)CA-GrQc与CA-HepTh.这两组数据集分别为广义相对论和量子宇宙学协作网和高能物理理论协作网，取自电子版arXiv.前者有5242个顶点和28980条边而后者有9877个顶点和51971条边.

2)soc-sign-bitcoinotc.这是在一个比特币OTC的平台上使用比特币进行交易的人的信任网.我们只关注于交易关系，对数据进行了处理.该图有5881个顶点和35592条边.

3)Brightkite是一个基于位置的社交网络服务提供商，用户可以通过签到共享他们的位置.该数据集有58228个顶点和428156条边.

4)soc-Epinions1是一般消费者的“谁信任谁”的在线社交网络，以信任关系为边.该数据集有75879个顶点和508837条边.

实验在PC机上进行，本次实验的运行环境为：Windows10(64bit)，Intel Core i7-7700 4核心CPU，16GB RAM，NVIDIA GTX1060 GPU.

4.1.2 对比方法

基于本文提出的2-lists索引结构及2-lists-PDFS算法，需要对索引占用内存大小和算法查询时间进行比较.由于现有的工作中没有专门用来对可达性查询算法并行化的方法，现用以下几种方法对比：

1)DFS：传统的深度优先搜索算法.

2)PDFS[22]：一个基于多核的深度优先搜索算法，使用传统的邻接表作为索引.

3)GRAIL[26]：一个基于可扩展标签索引的串行可达性查询算法.

为了进一步验证存储效率和预处理效率的提升，将对DFS、Grail和2-lists 3种索引结构的构造时间和所耗内存大小作比较；为了验证可达性查询的效率，对DFS、PDFS、Grail和基于2-lists-PDFS分别计算一个顶点的可达顶点，和两个顶点的共同可达顶点，将查询效率进行比较；最后，对4种算法的总计时间进行比较.

4.2 实验结果

本小节将对上一小节提出的几种比较方法的结果进行阐述.首先是DFS、Grail和2-lists这3种算法构建索引结构所耗时间的对比.

表3为3种方法构建索引需要的时间的对比，PDFS算法和DFS算法用的均是邻接表，在此表中只对后者进行列举.可以看到，本文提出的2-lists索引的构建的时间消耗最小，因为在构建2-lists索引时，通过边表可以用时间复杂度O(1)的随机访问来查找到对应的顶点，构建索引的时间复杂度为O(|V|+|E|)，而构建邻接表时，每次都需要查找顶点所在的位置，构建索引的时间复杂度为O(|V|×|E|)，而在Grail算法中，计算强连通分量和标签集为构建索引带来了不少的时间消耗.

表3 不同数据集上3种方法的构建索引的时间(s)

如表4所示，由3种算法根据不同种类的输入图所构建的索引结构所占内存大小不同，本文提出的2-lists索引结构空间消耗小于Grail但是却高于传统的邻接表.如公式(3)所示，2-lists所占内存空间大小根据图顶点和边的数量呈线性变化，而Grail算法需要计算图中的强连通分量进行图压缩后，再生成相应的标签，但压缩图只对图进行搜索时起到减枝的作用，实际上并没有将图的规模变小，所以生成的标签集会直接导致索引空间消耗增加.传统邻接表由于其只存储了最基本的边和顶点的相关信息，所以在空间消耗方面有着较大的优势.

表4 不同数据集上3种索引所占内存大小(KB)

图5为4种方法在5种数据集上查询效率的比较.如图5(a)所示，为对某一个顶点的所有可达顶点的查询，本文提出的并行化深度优先搜索算法的效率最高，其中，传统的深度优先搜索算法效率最低，本文提出的算法要高出其35%至70%的效率.相较于Grail算法，本文提出的算法要高出13%到43%的效率.相较于PDFS算法，本文提出的算法要高出11%到21%的效率.如图5(b)所示，为对两个顶点的共同可达顶点的查询，每组数据集都任意选出两个顶点，首先确保它们之间存在共同可达顶点，再进行查询.从图中看出，与单个顶点可达顶点查询相同，2-lists-PDFS算法的效率优于其他3种算法.

图5 不同数据集上4种方法的查询时间

表5和表6为5组数据集上4种方法测试的总耗时，包括构建索引的时间和查询的时间.可以看出，PDFS算法由于在构建索引效率过低，导致其总时间与传统DFS算法差距并不明显.而Grail算法和2-lists-PDFS算法的效率因为选择适当的索引没受太大影响.上述所有实验可以得出，我们的算法在存储开销和查询时间方面优于其他几种方法.

表5 不同数据集上4种方法的可达顶点查询总时间(s)

表6 不同数据集上4种方法的共同可达顶点查询总时间(s)

5 结束语

通过表5和表6可以得知，在对图数据进行研究时，构建一个合适的索引，与研究算法一样重要，平衡空间消耗与算法的时间消耗，依然是对图查询算法研究的重点.针对已有的图查询算法其索引结构过于复杂，传统串行算法不能适用于多核处理器的问题，本文提出了基于2-lists索引的并行化图查询算法，并在5组真实的数据集上进行了验证，实验结果表明，本文的工作比其他算法的表现更好.但本文仍有不足，对社交网等数据在实际应用场景的实时变化并未过多考虑，在未来的工作中将重点关注增量或减量带来的图查询问题.