基于参考节点嵌入的图可达性查询

摘要：针对k步可达性查询算法无法解决带距离约束的图可达性查询问题，提出基于参考节点嵌入的图可达性查询算法。首先，从所有节点中选出极少数有代表性的全局参考节点，预先计算所有节点与全局参考节点之间的最短路径距离；然后，采用最短路径树和范围最小值查询技术求得局部参考节点；接着，利用三角不等式关系得到查询点对距离范围；最后，根据查询条件中的距离值与查询点对距离范围上、下限值的大小关系，可快速得出可达性结论。针对社会关系网络和公路网络数据，将所提算法与Dijkstra算法、KReach算法进行实验对比测试。相较于KReach算法，其索引建立时间小4个数量级，其索引规模小2个数量级；相较于Dijkstra算法，在公路网络和社会关系网络中，直接得出可达性结论的比例分别为92%和78.6%，其查询时间大大缩短，分别降低了95.5%和92%。实验结果表明：所提算法能够通过使用较小的索引开销，实现在线查询计算复杂度的降低，可很好地解决既适用于有权图又适用于无权图带距离约束的可达性查询问题。

关键词：

k步可达性查询；带距离约束的图可达性查询；参考节点嵌入；三角不等式关系；最短路径树

中图分类号： TP301.6 文献标志码：A

0引言

针对图G=（V，E）中任意两个节点间的路径存在性进行判定，称为图的可达性问题。如果两点之间存在路径，则称u可达v，简记u v。图中节点间可达性判定，在现实很多领域有着广泛的应用，例如社交网络、生物网络、地理导航、Internet路由、可扩展标记语言（Extensible Markup Language， XML）索引、基于资源描述框架（Resource Description Framework， RDF）的本体查询等。如何有效地回答可达性查询问题成为目前研究的热点。

区别于传统图可达性查询问题[1-5]回答一个节点t是否可达另一个节点s，k步可达性问题研究[6-11]在很多现实网络中有着更为重要的意义[12]，k值大小直接反映节点s对节点t影响的程度。k步可达性查询问题回答是否存在一条从节点t到节点s的路径，路径长度不超过k步，如果存在，则用tk s表示，在此称为k步可达性问题。例如，在一个无线网络或者传感器网络中，广播消息在任何一次转发过程中都有可能丢失，经过多次的转发，接收的概率指数级降低。在这种情况下，两个节点之间是否可达实际意义不大，应该更加关心在k步两点之间是否可达，它可反映一个节点对另一个节点的影响程度。还有一种情况是：在社会关系网络中，由于六度分隔理论，任意两个陌生人最多通过6个人一定能相互认识，因此更为关心的应该是两人之间能否通过极小的几步可达。虽然经典可达性问题可以看作k步是否可达的一种特殊情况（k=∞），但是k步是否可达不是简单地从经典可达性问题导出，因为k步是否可达性问题更具有挑战性，需要解决更多的问题。

本文研究的既不是传统的可达性查询问题，也不是k步可达性查询问题，而是带距离约束的可达性查询问题，与k步可达性查询问题通常只能针对无权图，回答一个节点经过k条边是否可达另一节点的问题所不同的是：带距离约束的可达性查询可回答两节点之间在k值距离范围内是否可达，既适用于无权图也适用于有权图。例如，用户可以查询“广州到深圳在150公里之内是否可达”。带距离约束的查询比一般的可达性查询，以及近年来研究较多的无权图上k步可达性查询问题更具有实际意义。针对带距离约束的可达性查询问题，本文提出一种简单高效的处理方法――参考节点嵌入机制[13]，其核心思想为：从图中所有节点中选出有代表性的参考节点，预先计算出参考节点到所有节点之间的最短路径距离，然后根据三角不等式关系，计算出待查询两节点之间距离的上、下限值，根据k值大小，在绝大部分的情况下可迅速判断距离k值内是否可达，在不可判断的情况下，再进行最短路径距离计算，通过精确的距离来判断是否可达。由于选择的参考节点是所有节点中很小一部分，因此只需要极小的预存储空间。基于图可达性查询问题，本文的工作概括起来主要有以下几点：

1）对图可达性查询问题（包括传统可达性问题及k步可达性查询问题）的研究现状进行了总结。

2）针对带距离约束的可达性查询问题，提出一种基于参考节点嵌入的索引方法，通过索引可快速确定查询点对之间的距离范围，比较k值与距离范围的上、下限值之间的大小关系，在绝大部分情况下，可以直接给出可达性结论，无需进行最短路径距离的精确计算，使得查询效率更为高效。

3）为了缩紧距离范围上、下限值，引入局部参考节点，使用最短路径树及范围最小值查询技术，设计了基于参考节点嵌入的图可达性查询算法。

4）在数字参考书目和图书馆项目（Digital Bibliography & Library Project， DBLP）图和公路网络图数据上进行实验，实验结果对直接给出可达性结论的比例和查询时间进行分析。本文设计的算法查询时间位于2ms～6ms，70%～92%的查询都可以基于本文设计的索引快速给出可达性结论。

5）选取一种k步可达性查询算法――KReach与本文带距离约束的可达性查询算法，在DBLP无权图上进行实验，实验结果从索引构建时间、索引大小及查询响应时间等指标进行分析。实验结果显示，本文的方法在建立索引的时间和索引的空间开销上比KReach分别低了4个和2个数量级，而查询时间比KReach慢了4个数量级；但是本文方法可以适用于有权图和无权图，而KReach只能回答无权图上的可达性，因此本文的方法具有更为广泛和实际的应用价值。

1图可达性问题研究现状

对于一个具有n个顶点、m条边的图，任意的两个节点u和v，如果存在最短路径，则节点u到节点v可达，否则不可达。当图的规模比较小时，可使用最短路径算法或深度优先遍历（DepthFirst Search， DFS）算法来实现图可达性查询问题。其缺点是查询时间复杂度过高，对于大图和超大图而言，难以应用到实际中。

另外有一种简单的方法是：预先计算出图中节点间的可达性情况――图邻接矩阵的传递闭包，并将其存储下来，当查询图中任意两个节点u和v之间是否可达，只需查询节点u的传递闭包即可，如果包含节点v，则说明节点u和节点v之间可达，否则不可达。这个方法可在常数时间内完成可达性查询问题，由于预先计算的时间复杂度较大，为O（n3），预存的空间复杂度达到O（n2），当图更新时需要重新计算传递闭包，因此也难以应用到实际中。

针对图可达性查询问题，常常通过给图中节点作标记的方法（Labeling Scheme）[14]来解决，主要有3种代表性方法：1）位向量标记方案（Bit Vector Labeling Schemes）。该方案预先计算所花费的时间复杂度为O（n），预存的空间复杂度为O（n2），查询时间复杂度达到了O（n），由于标记长度依赖于节点个数，因此不适用于图更新的情况。2）前缀标记方案（Prefix Labeling Scheme）。该方案的优点是可以动态适应图的更新，但是节点间可达性查询依赖于字符串的操作，使之不易优化，并且从树扩展到图时，节点的标记数量会呈爆炸式增长。3）区间标记方案（Interval Labeling Scheme）。该方案的主要思想是先构造一棵生成树，并给树中节点作好标记，接着对节点按照反拓扑顺序进行标记，并且通过图中的非树边对其向上复制，以保存可达性信息，通常处理类似树或森林结构的图问题比较有效。其缺点是由于标记采用自然数，对于插入等动态更新操作显得繁琐。

近几年，为了提高图可达性查询效率，大量可达性索引方法被相继提出[1]，这些方法旨在索引规模、查询时间以及构建时间三个方面取得平衡。可达性索引研究的热点集中在大规模图数据可达性查询处理、动态图数据可达性处理和受限可达性查询处理。

同时，存在几种基于经典可达性查询问题拓展的研究方向：1）不确定图上的可达性查询研究[5]，该问题在现实中有着广泛的应用，例如生物学研究中，通常要研究蛋白质交互网络中任意两个蛋白质分子间是否有交互作用及交互强度的交换信息；为了在社交网络中推荐好友，需要预先知道用户之间的关联关系等。2）带条件限制的可达性查询研究[15-17]，两点之间的边必须带有某种标签属性。

以上都是针对两点之间是否可达进行研究，目前出现一个新的研究热点，判断两点之间在k步之内是否可达，即k步可达性查询问题，此研究具有更大的实际意义。例如：在社交网络，通常要作的是以某人为起点查找到离他最近的若干个人，以此来寻找比较近的朋友或者合作关系。

现今求解k步可达性查询问题方法主要有4大类：1）基于图遍历的求解方法，该方法按照遍历的规则从顶点u出发判断在k步之内是否可达顶点v，广度优先遍历（BreathFirst Search， BFS）按照通过已找到的顶点和未找到的顶点之间的边向外扩展，不会出现深度优先遍历（DFS）算法中的回溯现象，此类方法效率低下。2）基于区间标签求解方法[6-7]，典型代表是经随机间隔标记的图可达性索引（Graph reachability indexing via RAndomized Interval Labeling， GRAIL请补充GRAIL和PLL的英文全称。）方法[6]，其基本思想是给每一个顶点v附加两个区间标签L1和L2，这两个区间分别包含所有v可达顶点对应的区间，用这种方法来回答k步可达性查询时，若u和v的区间满足包含关系，但u的出度非常大且可达v的孩子顶点很少时，系统需要访问u的大量孩子顶点，最终递归处理会访问大量无用顶点，最坏情况下和基于广度优先遍历来求解k步可达性查询的代价一样低效。BiRch算法[7]在GRAIL方法上作了一定的改进，提出了一种双向搜索策略，并且设计了基于双向广度层数和双向拓扑层数的剪枝策略来辅助过滤，以减少需要访问的顶点数量。3）基于最短路径的方法[8，11]，典型代表是剪枝参考标记（Pruned Landmark Labeling， PLL）[8]方法，在进行深度优先遍历时事先计算出每个节点的距离标签，利用剪枝和位操作并行运算两个技术来进行相应的优化。4）基于k步索引的方法[9-10]，文献[9]中设计的KReach算法，其基本原理是先根据原图的一个顶点覆盖集合，建立k步可达索引，实现k步可达性的查询。算法缺陷在于索引是根据某一个k值进行构建，对不同的k值要作不同的索引。例如，如果索引基于k=3进行构建，只能回答查询点对之间3步是否可达，无法回答其他步数之内是否可达的查询问题。在文献[10]中，算法虽然作了一定的改进，可以回答任意k步是否可达的查询问题，但是，建立索引的开销随之升高，在图比较稠密情况下，仍然存在索引规模急剧膨大的问题。

然而，在实际应用中，例如公路网络，往往不是查询两点之间经过多少条边是否可达，而是判断在多远路程之内是否可达。在这种情况下，此类问题，只能通过带距离约束的可达性查询算法加以解决。本文提出的基于参考节点嵌入的图可达性查询算法属于带距离约束的可达性查询算法，该算法具有通用性，对无权图、有权图都适用。当查询的图为无权图时，边上的权值为1，此时带距离约束的可达性查询算法变为k步可达性查询算法，此时的k值即表示边的条数，也代表两点之间的距离。当查询的图为有权图时，本文算法可以回答两点之间在某个距离范围是否可达，可解决k步可达性查询算法无法解决的查询条件中带有距离值的可达性问题。

2基于参考节点嵌入的图可达性查询

一个图通常表示为G=（V，E，w）。其中V是顶点的集合，E是边的集合，w：E R表示一个边权重函数，代表一条边映射成一个实数域上的权重。w（u，v）是一个正数，它表示节点u到节点v的距离长度，如果一个图是无权图，那么每条边的权w（u，v）就是1。

假设定义：n=|V|，m=|E|，则n、m分别表示图中节点数和边数，对于一个节点对a，b∈V，p（a，b）=（a，v1，v2，…，vl-1，b）表示a、b之间对应的一条路径，对于有向图而言，a为起点，b为终点，其中{a，v1，v2，…，vl-1，b}V，{（a，v1），（v1，v2），…，（vl-1，b）}E，|p|=l，l表示路径p的长度，对于无权图而言，l表示路径上边数之和，对于有权图而言，l表示路径上各边长度之和。假定SP（a，b）表示节点a到节点b所有路径的集合；O（a，b）表示节点a到节点b最短路径距离，则O（a，b）的计算如式（1）所示：

O（a，b）=minp∈SP（a，b）|p|（1）

在回答带距离约束的可达性查询问题时，并不是所有情况下都必须计算出精确的最短路径距离。如果能够快速计算出两点之间最短路径的范围区间，在绝大部分情况下通过距离k值和距离范围上、下限值大小关系，直接给出可达性结论，而在极少数情况下，需要精确计算出查询点对之间的最短路径距离，与k值进行比较，给出可达性结论，这将极大提高图可达性查询的效率。

基于参考节点嵌入的图可达性查询算法如算法1所示。

算法1基于参考节点嵌入的图可达性查询算法。

有序号的程序――――――――――Shift+Alt+Y

程序前

输入：一个有向图G=（V，E，w）、查询点对a和b、距离值k。

输出：一个表达a在k值距离内是否可达b真假性的逻辑值。

1）

range（a，b，&upper，&lower）/*算法2或算法4实现*/

2）

if （k

3）

return false；

4）

if （k≥upper）

5）

return true；

6）

if （k≥lower&&k

7）

{ dist=shortestpathdistance（a，b）；

8）

if （dist≤k）

9）

return true；

10）

else

11）

return false；}

程序后

算法1的第1）行代码为求查询点对最短路径距离范围区间上、下限值range函数的调用。range函数如果只是依据全局参考节点来确定距离范围，则由2.1节的算法2加以实现。为了进一步提高距离范围的精度，使得在作查询时直接给出可达性结论的可能性变大，需要在全局参考节点基础上，按照某种选择策略选出与查询点对位置相关的局部参考节点，根据全局和局部参考节点两个信息，计算出更为精确的查询点对距离范围区间，此时range函数则由2.2.4节的算法4加以实现。

2.1最短路径距离范围区间的确定

本文将参考节点嵌入思想引入到图可达性查询研究中，利用预先计算出参考节点与其他所有节点之间的距离，快速计算出两点之间距离的上、下限值，从而确定距离范围区间。本文引入的参考节点嵌入思想来自于文献[13]，该思想用于最短路径距离估算，其主要原理是：从所有节点中选择少量有代表性的参考节点，预先计算出参考节点与其他所有节点之间的距离，并且存储下来，在需要计算两点距离时，通过预存的距离，并利用三角不等式关系估算出两点之间的近似距离。参考节点嵌入思想广泛应用在社会关系网络、公路网络、因特网等网络数据中，例如为了减少客户端的访问延迟，在因特网中查询最近的服务器，或者在公路网络中查询两地之间的最短路径。

在此约定，本文讨论的带距离约束的图可达性查询算法，k值代表距离值，不是步数值。假设选定的参考节点集合S={l1，l2，…，ld}V，对于集合中每一个li∈V，预先计算出参考节点与所有节点之间的最短路径距离，对于图中每个节点v∈V，使用一个d维的向量来表示该点到所有参考节点的最短路径距离：

D（v）=〈ο（l1，v），ο（l2，v），…，ο（ld，v）〉

根据预存距离值，基于三角不等式关系，可获得每一个参考节点对应的查询点对a、b距离范围的上、下限值，最终从所有的下限值中取最大值，从所有的上限值中取最小值，最终形成查询点对a、b距离范围区间，如式（2）、（3）所示：

o（a，b）≥maxli∈S {|ο（li，a）-o（li，b）|}（2）

ο（a，b）≤minli∈S {ο（li，a）+ο（li，b）}（3）

当查询点对的距离上、下限值确定之后，可达性判断结论的给出可以分以下3种情况：

1）当k

2）当k≥minli∈S {ο（li，a）+ο（li，b）}时，说明k值等于或者大于距离的上限值，此时可以马上给出两点之间可达的结论，此处对应算法1中第4）行代码条件成立的情况；

3）当k

如果给出的距离范围比较小时，大部分情况下都可以使用第1）、2）情况直接给出可达性结论，如果给出的距离范围太大时，k值位于上、下限值之间的概率变大，无法利用第1）、2）情况直接给出判断，必须进入第3）种情况，在线计算两点之间的最短路径距离，因此，距离范围的大小直接影响到查询效率，当参考节点选择策略比较优化时，则通过三角不等式给出的距离范围更小，距离上、下限值更接近真实的距离值。查询点对最短路径距离范围区间的确定通过算法2实现，如下所示。

算法2确定查询点对最短路径距离范围区间算法。

有序号的程序――――――――――Shift+Alt+Y

程序前

输入：一个有向图G=（V，E，w）、查询点对a和b。

输出：距离范围区间上限值upper、下限值lower。

1）

Compute a vertex set S={l1，l2，…，ld}V/*求参考节点集合S*/

2）

for each v∈V do

3）

Compute vector D（v）=〈ο（l1，v），ο（l2，v），…，ο（ld，v）〉

4）

for each li∈S do

5）

Compute |o（li，a）-o（li，b）|

6）

Compute o（li，a）+o（li，b）

7）

lower=maxli∈S {|ο（li，a）-o（li，b）|}

8）

upper=minli∈S {ο（li，a）+o（li，b）}

9）

return upper，lower

程序后

算法2第1）行代码实现参考节点的选择。如今选择参考节点的方法是主要有随机选择法、各类基于图的启发式算法：例如基于度、基于中介中心性（betweenness centrality）、基于接近中心性（closeness centrality）等启发式算法。尽管各种启发式算法都致力于最优化参考节点的选择，但是参考节点的选择都没有考虑到与查询点对位置之间的关系，以至于可能出现两个查询点对之间很近；但与选出的参考节点很远，根据三角不等式算出的距离上、下限值范围过大的情况。目前，在最短路径估算方面，一种与查询相关的局部参考节点嵌入机制[18]被提出，此方法提供了更为精确的最短路径距离估算。此方法可以很好地应用于带距离约束的图可达性查询问题中，更为精确地定位距离上、下限值。

2.2与查询相关的局部参考节点嵌入机制

2.2.1与查询相关的局部参考节点概念

通过图说明与查询相关的局部参考节点概念，如图1所示。在图1中，实线代表两个点之间的一条边，虚线则表示两点之间有一条包含多个中间连接点的路径，其中中间连接点信息省略，（a，e， f，g，b）路径是a和b之间的最短路径。

根据式（6）、（7）进行加法和减法运算，式（4）可变成式（8），如下所示：

o（c，a）-o（c，b）≤o（a，b）≤o（c，a）+o（c，b）+2o（l1，c）（8）

对比式（5）、（8），可以发现全局参考节点与局部参考节点给出的查询点对a、b的下限值一样，不同的是上限值。l1参考节点给出的上限值比c参考节点给出的上限值更大（前者比后者大2o（l1，c）），因此需要结合局部参考节点信息对范围区间的上限值进行修正，修正为o（c，a）+o（c，b），修正的结果再结合式（6）、式（7），查询点对a、b的上限值如式（9）所示：

o（a，b）≤o（l1，a）+o（l1，b）-2o（l1，c）（9）

通过以上分析，可以发现局部参考节点的引入，可以使得查询点对a、b的上限值变小，接下来的问题就转化为给定一个任意查询点对及全局参考节点集合S，如何找到与每一个全局参考节点相对应的局部参考节点，并最终从计算出来的所有上限值中取最小值，获得新的距离范围上限值，如式（10）所示：

ο（a，b）≤minli∈S {ο（li，a）+ο（li，b）-2o（li，c）}（10）

局部参考节点的引入让距离的上限值变得更小，使得距离范围区间更为紧缩。每一个局部参考节点都和某一个全局参考节点相对应。以图1为例，相对于全局参考节点l1而言，离节点a、b更近的节点c称为与查询点对a、b相关的局部参考节点。同理，相对于全局参考节点l2、l3而言，节点d、h称为与查询点对a、b相关的局部参考节点。

2.2.2基于局部参考节点的最短路径树

为了找到与每一个全局参考节点相对应的局部参考节点，可通过以全局参考节点为根的最短路径树加以实现。

定义1假定一个图表示为G=（V，E，w），以r（r∈V）为根节点的最短路径树（Shortest Path Tree， SPT）是一棵这样的生成树：从r到每一个节点v（v∈V）都是一条r到v之间最短的路径，并且这条最短路径的长度是r到v之间的最短距离，如图2所示。

图2是针对图1中全局参考节点l1的一个最短路径树。注意从图1导出的以节点l1为根的最短路径树并不唯一。通过图2可以发现节点c比节点l1更为接近节点a、b，是与查询相关的局部参考节点，它即为a、b的最小共同祖先（Least Common Ancestor， LCA）节点。

定义2假设T为一棵根为l，带有n个节点的树，所谓树T中节点u，v的LCA节点是一个离根最远的节点u，v的共同祖先节点，它可由函数LCA（u，v，l）计算获得。

因此，图2中相对于全局参考节点l1而言，与查询点对a、b相关的局部参考节点c，可由函数LCA（u，v，l1）计算获得，因此问题又转化为求根节点为l1的最短路径树中节点a、b的最小共同祖先问题。

此时a、b两点之间距离上限值由式（11）获得：

2.2.3范围最小值查询技术

在参考文献[19]中介绍的范围最小值查询（Range Minimum Query， RMQ）技术，可以快速找到一个最短路径树中两个节点之间的LCA节点。

定义3假定A为一个长度为n的一维数组：A[1，2，…，n]，范围最小值查询RMQA（i， j）表示返回数组A[i，…， j]最小元素值，其中i、 j表示数组的下标值，其范围是：1≤i≤j≤n。

由于节点a、b的LCA是对树T进行深度优先搜索时，在访问节点a和节点b之间离根最近（节点深度最小）的那个节点，因此，两个节点之间的LCA节点问题又转化为以下最小值查询问题：

1）由于对由n个节点构成的树T作欧拉环游深度优先遍历时，需要对n-1条边的每条边作两次访问，因此，用数组trace[1，2，…，2n-1]来记录遍历过程中节点的信息。图2的最短路径树，对应的trace数组为：trace=（l1，…，c，e，a，…，h，…，l3，…，h，…，a，e， f，e，c，d，…，l2，…，d，g，b，g，d，c，…，l1）。

2）用数组L[1，2，…，2n-1]记录trace数组中对应节点在树T中的深度值，假定根节点的深度值为0，离它一步可达的孩子节点深度值则为1，以此类推。

3）用数组stamp[1，2，…，n]记录树T中n个节点在深度优先遍历时在数组trace中第一次出现的下标值，即stamp[a]=mini{trace[i]=a}，a∈V。

因此，在以全局参考节点l1为根节点的最短路径树中，与查询点对a、b相关的局部参考节点的计算式如下：

LCA（a，b，li）=trace[arg minstamp[a]≤i≤stamp[b]L[i]]=trace[RMQL（stamp[a]，stamp[b]）]（12）

2.2.4与查询相关的局部参考节点选择算法

算法2中第1）行代码，是基于图的启发式算法进行参考节点的选择，为了找到更为紧缩的距离范围区间，需借助局部参考节点对距离范围区间进行修正，局部参考节点的获得通过与查询相关的局部参考节点选择算法加以实现，如算法3所示。

算法3与查询相关的局部参考节点选择算法。

有序号的程序――――――――――Shift+Alt+Y

程序前

输入：一个有向图G=（V，E，w）、一个全局参考节点l∈S（S={l1，l2，…，ld}V）、查询点对a和b。

输出：局部参考节点c。

1）

Create a shortest path tree rooted at a vertex l

2）

Create an array trace[2*n-1]

3）

Create an array L[2*n-1]

4）

Create an array stamp[n]

5）

i=stamp[a]

6）

j=stamp[b]

7）

t=RMQL（i， j）

8）

c=trace[t]

9）

return c

程序后

算法3可以计算获得查询点对a、b对应于全局参考节点l的局部参考节点，该算法可以用来定义求局部参考节点的函数LCA，c=LCA（a，b，l），根据式（10）可知，查询点对a、b距离的上限值要作修正，因此确定查询点对最短路径距离范围区间的算法2需要修改为算法4，如下所示。

算法4基于局部参考节点确定查询点对距离范围区间算法。

有序号的程序――――――――――Shift+Alt+Y

程序前

输入：一个有向图G=（V，E，w）、查询点对a和b。

输出：距离范围区间上限值upper、下限值lower。

1）

Compute a vertex set S={l1，l2，…，ld}V/*求参考节点集合S*/

2）

for each v∈V do

3）

Compute vector D（v）=〈ο（l1，v），ο（l2，v），…，ο（ld，v）〉

4）

for each li∈S do

5）

c=LCA（a，b，li）/*LCA函数由算法3实现*/

6）

Compute |o（li，a）-o（li，b）|

7）

Compute o（li，a）+o（li，b）-2o（li，c）

8）

lower=maxli∈S {|ο（li，a）-o（li，b）|}

9）

upper=minli∈S {ο（li，a）+o（li，b）-2o（li，c）}

10）

return upper，lower

程序后

2.3时间复杂度分析

2.3.1离线计算时间复杂度分析

计算一个点到其他各点最短路径距离时间复杂度为O（n*log n+m），在计算最短路径的同时，以该节点为根的最短路径树也自动生成。另外，对每一个全局参考节点而言，建立一个对应的RMQ查询表的时间复杂度为O（n），两个部分之和为O（n*log n+m）。假设集合S为全局参考节点集合，d=|S|代表全局参考节点个数，因此，总时间复杂度为O（d*n*log n+d*m），请注意d是一个比较小的常数，由于通常情况下dn，则时间复杂度大约为O（n*log n+m）。

2.3.2离线计算空间复杂度分析

构建与查询相关的局部参考节点嵌入的最短路径树需要的空间，可以分为以下两个部分：

1）对于每个全局参考节点，需要存储预先计算到各个节点之间的最短路径距离，因此，空间复杂度为O（d*n）。

2）对于每个全局参考节点，需要计算对应的最短路径树，以及在对其进行深度优先遍历时，生成trace、L、stamp数组。以上每个部分的空间复杂度都为O（n），则所有全局参考节点需要的空间复杂度为O（d*n）。

将以上两个部分求和，总的空间复杂度为O（d*n）。

2.3.3在线查询的时间复杂度分析

分两种情况来讨论：

1）如果可以通过上、下限值给出可达性结论，则查询的时间复杂度取决于式（11），对于每一个全局参考节点而言，有3次查询预先计算的最短路径距离，时间复杂度为O（1）；另外，为了找到查询点对的最小共同祖先（LCA），通过RMQ算法实现，其时间复杂度为O（1），因此考虑到d个全局参考节点，总共的时间复杂度为O（d）。

2）当k值在上、下限值之间，需要进一步计算两点之间的最短路径距离来进行可达性判定时，时间复杂度则为O（n*log n+m）。

最好的情况是可通过距离上、下限值直接给出可达性结论，其时间复杂度O（d），比起通过直接求两点之间最短路径距离，给出可达性判断的时间复杂度O（n*log n+m）而言，复杂度大大降低，因此使用一个合理的参考节点嵌入机制，可使得大部分点对之间可达性判断属于以上第1）种情况，其时间复杂度可大大降低。

3实验结果与分析

3.1实验环境

实验使用机器的基本配置为Intel Xeon X5550 2.67GHz CPU，48GB内存，操作系统为Linux。本文采用的实验数据来源于两个真实的图――DBLP数据集和纽约公路网络数据集。其中，DBLP是一个计算机领域内对研究的成果以作者为核心进行集成的计算机类英文文献的数据库系统。实验使用的DBLP数据集选取数据库、数据挖掘、信息检索和人工智能这四个研究领域的参考文献数据，该数据组成了一个反映四个领域内最高产作者合著者关系的大图，该图是无权图，每条边权值都为1，其中，每个节点表示一个作者，每条边表示两个作者之间的合著关系。纽约公路网络数据属于公路网络，是有权图，每条边的大小反映两个点之间距离的远近。

实验分为两大部分：第1部分是本文设计的基于参考节点嵌入的图可达性查询算法与Dijkstra算法进行对比；第2部分是本文算法与k步可达性查询算法的一个代表KReach算法进行对比。所有算法都基于Microsoft Visual C++实现。

3.2第1部分实验――算法性能测试

第1部分实验将从两个方面进行测试：

1）使用Dijkstra算法计算出所有查询点对之间精确距离进行可达性判断，与基于参考节点嵌入的可达性查询算法进行可达性判断，比较这两种算法给出可达性结论运行时间的长短。

2）使用基于参考节点嵌入的可达性查询算法时，计算出所有点对之间可达性判断中，通过k值大于等于上限值或者小于下限值的关系直接给出可达性结论的比例。

3.2.1时间测试

针对两个数据集，取2000个点构成图。对于每一个图而言，采用下面的方法产生500个查询用于测试：随机产生500个点对表示出发点和目的点。每个查询的k值根据整个图中所有点对之间的最短路径距离最小值和最大值之间随机产生，这样能确保查询点对之间可达性结论均匀覆盖可达和不可达情况。这两个图所有点对之间的最短路径距离长度分布如图3～4所示。从图3可以看出DBLP图所有点对之间距离范围为1～15，k值应取1～15的随机数；从图4可以看出公路网络图所有点对之间距离范围为1～226，k值应取1～226的随机数。

针对两个不同的图，分别作两次数据测试。每次数据测试，确保均在相同的查询数据前提下，使用Dijkstra算法和基于参考节点嵌入的可达性查询算法（以下简称可达性查询算法）进行可达性判断，采集两者各自运行时间，具体数据如下表1所示。其中：d表示参考节点数目；tz表示平均每一个点对使用Dijkstra算法运行的时间；tk表示平均每个点对使用可达性查询算法运行的时间。

从表1数据可以发现，不管是DBLP图还是公路网络图，其运行时间都大大缩短，其中公路网络的效果更为明显。相较于直接计算最短路径距离进行可达性判断，当d=20时，两者的运行时间都是最小值。相对于最短路径算法，在DBLP图和公路网络图中，运行时间分别降低了92%和95.5%。

接下来，将以上运行时间随着参考节点的增加而变化的趋势用图表直观表示出来，如图5所示。从数据的变化趋势可以发现：随着参考节点数目的增加，可达性查询算法的运行时间开始呈减少趋势，原因在于参考节点数目越多，确定距离上、限值的范围就更为精确，则直接给出可达性判断的情况就越多，因此运行时间越来越少，但是到达一个最低点之后，运行时间又呈增加趋势，原因在于随着参考节点数目的增加，用于确定距离上下限范围的开销也变得越大。结合表1数据和图5数据的变化趋势可以看出，两个数据集都是d=20时运行时间最短。

3.2.2比例测试

针对两个数据集取2000个点构成图，分别作两次数据测试。每次都随机产生500个点对和对应合理的k值，统计出通过k值与上、下限值的关系直接给出可达性结论的点对数占总点对数的比例，其值用percentage表示，该值随着参考节点数目（d值）的变化也发生改变，如表2所示。

从表2数据可以发现：percentage值对DBLP图而言偏低，最高78.6%，最低69.6%；对公路网络图而言，最高92%，最低79.2%。分析其原因在于这两个数据集合属于不同类型的数据：DBLP数据是小半径的社会关系网络数据，其符合六度分隔理论，点对之间的距离差别不大，只有通过提高参考节点的数目来收紧上、下限值，获得更为精确的距离范围，因此相较于公路网络图而言，直接获得可达性结论的比例值偏低；而公路网络由于是有权值的图，两点之间的距离跨度较大，用同样数量的参考节点，可以更高比例直接回答可达性结论。

接下来，将2000个点构成的DBLP图和公路网络图的percentage值以图表形式显示，如图6所示。从图6可以发现比例值都是随着参考节点数目的增加而增加，原因在于参考节点数目越多，距离上、下限值就越精确，通过k值与上、下限值的关系直接给出可达性结论的情况就越多，因此，提高参考节点的数目可提高直接给出可达性结论的比例。

通过时间和比例值数据的测试，发现参考节点数目的确定非常重要：参考节点数越多，直接给出可达性结论的比例就越高，运行时间也会随之减少；但是参考节点数达到一个值之后，用于给出距离上、下限值的开销也会越大，运行时间又会增加，因此选择合适大小的d值非常重要。此方法针对不同类型的数据，都可以达到减少运行时间的目的，直接给出可达性结论的比例用于点对之间跨度比较大的数据集，效果更好。

3.3第2部分实验――性能对比测试

由于KReach算法属于k步可达性查询算法，它只能处理无权图，因此本文设计算法与KReach算法只在无权图DBLP数据上作实验对比。衡量一个查询算法的性能不能只看查询时间长短，而要综合考虑索引建立时间、索引大小、查询时间三个方面因素。

针对同样的500个查询请求，实验采集两个算法的索引建立时间、索引大小、查询时间这3个指标数据，结果如表3所示。

从表3数据可以看出，本文设计算法除了查询时间，在索引建立时间和索引所占空间大小都有明显优势，索引建立时间比KReach算法低了4个数量级，索引大小比KReach算法小了2个数量级。原因在于KReach算法针对每一个k值都建立一个对应的索引，在查询条件固定一个k值时优势明显；但针对不同查询点对k值不同的情况下，要花费更大的代价建立对应的索引信息。KReach算法采取用索引建立时间和空间代价换取查询时间缩短的策略，在查询时只需要直接查询索引表即可，时间复杂度为O（1），而本文设计的算法在线查询的时间复杂度在2.3.3节有详细描述，最好情况下时间复杂度为O（d），最坏情况下为O（n*log n+m）。从表2的DBLP数据可以看出，直接给出可达性结论的点对数占总点对数的比例percentage值最大为78.6%，可在常量时间内查询索引表后进行简单计算即可给出可达性结论，然而，仍然存在21.4%查询点对落入最坏情况――需要在线计算最短路径距离给出可达性结论，因此总体的查询时间相较于KReach算法更长。然而，衡量查询算法性能好坏要综合考虑索引建立时间、索引大小、查询时间三个因素，不能单单只看在线查询时间长短，随着图规模的进一步加大，KReach算法建立索引的开销会急剧膨大，以索引建立时间和空间代价换取查询时间缩短的做法不太可取，并且本文算法适用范围更广，既适用于有权图又适用于无权图，因此综合比较，本文所提算法可被广泛地应用。

4结语

本文提出一种解决带距离约束的可达性查询问题的算法，该算法可以回答两点之间多少距离范围之内是否可达。相较于k步可达性查询算法只能在无权图上回答节点t在k步长之内是否可达节点s，带距离约束的可达性查询算法可以回答节点t在k值距离之内是否可达节点s，既适用于无权图也适用于有权图，该算法更具有更为广泛和实际的应用价值。本文的创新点在于将参考节点嵌入机制引入到图查询研究中，设计出用于解决带距离约束的可达性查询问题的算法――基于参考节点嵌入的图可达性查询算法，该算法的优点是索引规模小，索引建立时间短，大部分情况下可以通过查询索引表进行简单计算，直接给出可达性结论。今后工作的重点是在参考节点的选择策略方面作进一步的研究，更为快速和精确地确定两点之间距离的上、下限值，使得能够通过查询索引表直接给出可达性结论的比例提高，进一步缩短查询时间，提高查询效率。

参考文献：

[1]

富丽贞，孟小峰.大规模图数据可达性索引技术：现状与展望[J].计算机研究与发展，2015，52（1）：116-129.（FU L Z， MENG X F. Reachability indexing for largescale graphs： studies and forecasts [J]. Journal of Computer Research and Development， 2015， 52（1）： 116-129.）

[2]

CHEN Y J， CHEN Y B. Decomposing DAGs into spanning trees： a new way to compress transitive closures [C]// Proceedings of the 27th International Conference on Data Engineering. Washington， DC： IEEE Computer Society， 2011： 1007-1018.

[3]

SEBASTIAAN J V S， OEGE D M. A memory efficient reachability data structure through bit vector compression [C]// SIGMOD’11： Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2011： 913-924.

[4]

李世峰.大规模有向图的可达查询关键技术研究[D].沈阳：辽宁大学，2014：10-14.（LI S F. Research on key techniques of reachability query for largescale digraphs [D]. Shenyang： Liaoning University， 2014： 10-14.）

[5]

翟秋瑛.基于可达性的不确定图查询研究[D].哈尔滨：哈尔滨工业大学，2013：1-7.（ZHAI Q Y. The query research based on reachability of uncertain graph [D]. Harbin： Harbin Institute of Technology， 2013： 1-7.）

[6]

YILDIRIM H， CHAOJI V， ZAKI M J. GRAIL： scalable reachability index for large graphs [J]. PVLDB Journal， 2010， 3（1）： 276-284.

[7]

周军锋，陈伟，费春苹，等.BiRch：一种处理k步可达性查询的双向搜索算法[J].通信学报，2015，36（8）：50-60.（ZHOU J F， CHEN W， FEI C P， et al. BiRch： a bidirectional search algorithm for kstep reachability queries [J]. Journal on Communications， 2015， 36（8）： 50-60.）

[8]

AKIBA T， IWATA Y， YOSHIDA Y. Fast exact shortestpath distance queries on large networks by pruned landmark labeling [C]// SIGMOD’13： Proceedings of the 13th Special Interest Group on Management of Data Conference. New York： ACM， 2013： 349-360.

[9]

CHENG J， SHANG Z， CHENG H. KReach： who is in your small world [J]. Proceedings of the VLDB Endowment， 2012， 5（11）： 1292-1303.

[10]

CHENG J， SHANG Z， CHENG H. Efficient processing of khop reachability queries [J]. The VLDB Journal， 2014， 23（2）： 227-252.

[11]

WEI F. TEDI： efficient shortest path query answering on graphs [C]// Proceedings of the 2010 ACM SIGMOD International Conference on Management of data. New York： ACM， 2010： 99-110.

[12]

QIAO M， QIN L， CHENG H， et al. TopK nearest keyword search on large graphs [C]// Proceedings of the 39th International Conference on Very Large Data Bases. New York： VLDB Endowment， 2013： 901-912.

[13]

MICHALIS P， FRANCESCO B， CARLOS C， et al. Fast shortest path distance estimation in large networks [C]// Proceedings of the 18th ACM Conference on Information and Knowledge Management. New York： ACM， 2009： 867-876.

[14]

宋劲柯.FLS：一种支持更新的图可达性标记算法[D].上海：复旦大学，2009：1-3.（SONG J K. FLS： a labelling scheme to solve the reachability problem of dynamic updating graph [D]. Shanghai： Fudan University， 2009： 1-3.）

[15]

SAYED A， KAYED M， HAMMOSHI M. Efficient evaluation of reachability query for directed acyclic XML graph based on a prime number labelling schema [J]. Egyptian Informatics Journal， 2012， 13（3）： 209-216.

[16]

ZOU L， XU K， YU J X， et al. Efficient processing of labelconstraint reachability queries in large graphs [J]. Information Systems， 2014， 40（1）： 47-66.

[17]

陈明涵.不确定图上基于标签限制的可达性查询技术的研究[D].沈阳：东北大学，2013：10-17.（CHEN M H. Research on labelconstraint reachability queries in uncertain graphs [D]. Shenyang： Northeastern University， 2013： 10-17.）

[18]

QIAO M， CHENG H， CHANG L J， et al. Approximate shortest distance computing： a querydependent local lankmark scheme [J]. IEEE Transactions on Knowledge and Data Engineering， 2014， 26（1）： 55-68.

[19]

BENDER M A， FARACHCOLTON M. The LCA problem revisited [C]// LATIN’00 Proceedings of the 4th Latin American Symposium on Theoretical Informatics. Berlin： Springer， 2000： 88-94.