杜明 林铿 周军锋

摘 要：给定一个有向图，一个k步可达查询u→？kv用来回答在该图中是否存在一条从顶点u到顶点v且长度不大于k的有向路径。k步可达查询是一种基本的图操作并在过去十年间被广泛地研究。已有的k步可达查询算法仍存在许多弊端，例如不可达查询效率低，索引规模大和索引构建时间长等。本文针对上述问题提出了2种优化方法，分别是基于互逆拓扑序号以及基于等价顶点的图压缩方法.前者提高了不可达查询的效率，后者减少了索引规模和索引构建时间。实验结果表明，本文提出的方法可以有效地处理k步可达查询，并支持大规模数据的处理。

关键词： 有向图;k步可达查询;图压缩

文章编号： 2095-2163（2021）01-0008-07 中图分类号：TP301.6 文献标志码：A

【Abstract】Given a directed graph， a k-hop reachability query u→？kv is used to answer whether there is a directed path from vertex u to vertex v and the length of the path is not greater than k. The k-hop reachability query is a basic graph operation and has been extensively studied in the past years. Existing algorithms still have many drawbacks， such as being inefficient for unreachability queries， large index size and long index construction time. This paper proposes two optimization approaches to make improvements， i.e.， the mutual reversed topological order and the graph compression based on equivalent vertices. The former improves the efficiency of unreachability queries， and the latter reduces the index size and index construction time. The experimental results show that the proposed method can effectively improve the performance of k-hop reachability queries processing and support large-scale graph processing.

【Key words】directed graph; k-hop reachability query; graph compression

0 引 言

隨着互联网的快速发展，各种数据的规模日益庞大。图是一种常见的数据表示模型，其中每个实体被简单地抽象成图中的一个顶点，实体间的关系被抽象成2个顶点之间的一条边。图被广泛地应用于各类领域，如社交网络、通信网络、交通网络等等[1-3]。在图模型上的一个基本操作是回答2个顶点之间的可达性查询，即判断在图中是否存在一条从源顶点u出发到目标顶点v结束的一条有向路径。可达性查询在过去被广泛地研究[4-8]，然而在实际应用中，可达性查询仅能回答2个实体之间是否存在某种关系，而无法回答这种关系的强弱程度。

另一种更有价值的操作是回答2个顶点之间的k步可达查询[9-10]，即判断在图中是否存在一条从源顶点u出发到目标顶点v结束的一条有向路径，并且满足该路径的长度不超过k。……