带权大图上的K步可达性查询算法  

K-HOP REACHABILITY QUERIES ON WEIGHTED LARGE GRAPHS

作　　者：李文华 李盛恩[1] Li Wenhua;Li Sheng’en(School of Computer Science and Technology,Shandong Jianzhu University,Jinan 250100,Shandong,China)

机构地区：[1]山东建筑大学计算机科学与技术学院,山东济南250100

出　　处：《计算机应用与软件》2023年第7期26-33,共8页Computer Applications and Software

摘　　要：可达性查询作为图中最常用的基本操作,在生物信息学、智慧交通等领域应用广泛,但在一些现实问题中,仅仅进行可达性查询并不能满足人们对距离信息的需求,K步可达性查询应运而生。目前已有的K步可达性查询的处理对象为有向无环图,无法充分反映顶点间的距离信息,并且无环图并不符合交通网络等实际应用情况。针对以上问题,提出一种针对带权有向图的K步可达性查询算法。通过求解近似最小顶点覆盖集,分别构建了顶点覆盖集内索引和顶点覆盖集外的双向最短路径索引,有效避免了查询时的I/O操作,提高了查询效率。在10个数据集上进行对比实验,并通过比较索引构建时间、索引规模、查询时间等指标证明了该算法的高效性。Reachability query is one of the basic and common-used operation in graph data and widely-used in bioinformatics,intelligent transportation and so on.However,in some practical problems,the reachability query alone cannot meet people s demand for distance information,so the k-hop reachability query arises.At present,the processing object of the existing k-hop reachability query is the directed acyclic graph,which cannot fully reflect the distance information between vertices,and the acyclic graph does not fully reflect to the practical application such as traffic network.In order to solve the above problems,a k-hop reachability query algorithm for weighted directed graphs is proposed.By computing approximate minimum vertex cover set,indexes for vertex cover set and bi-directional shortest path indexes for vertex coverage set were constructed respectively,which effectively avoided I/O operation and improved query efficiency.Comparative experiments were carried out on ten data sets,and the efficiency of the algorithm was illustrated by comparing index construction time,index size,query time and other aspects.

关 键 词：带权大图 K 步可达性 顶点覆盖 图数据库 知识图谱 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]