一种高效的权值约束可达性查询处理算法  

An Efficient Algorithm for Reachability Query with Weight Constraint

作　　者：成梦佳 杜明[1] 周军锋 CHENG Meng-jia;DU Ming;ZHOU Jun-feng(Donghua University,Songjiang,Shanghai 200000,China)

机构地区：[1]东华大学,上海松江200000

出　　处：《新一代信息技术》2021年第9期1-7,共7页New Generation of Information Technology

摘　　要：基于权值约束的可达性查询是可达性查询的一种,用于回答在加权图上,给定两个查询的顶点之间是否存在一条路径,该路径上所有边的权值都满足给定的权值约束。现有的基于权值约束可达性查询的相关算法尽管查询响应时间较快,但是其构建的索引规模太大,无法在内存有限的情况下,处理规模较大的数据图。本文提出一种基于顶点的度构建2-hop索引的算法,来支持在有限的内存内高效地处理大规模数据图上的权值约束可达性查询。实验通过多个数据集证明,该方法能够有效降低索引的规模。The reachability query based on weight constraint is a kind of reachability query,which is used to answer whether there is a path between the vertices of given two queries on a weighted graph,and the weights of all the edges on the path satisfy the given weight constraint.The existing algorithms based on weight constraint reachability query have fast query response time,but the index size built by them is too large to deal with large scale data graphs under the condition of limited memory.In this paper,we propose a 2-hop index algorithm based on vertex degree to efficiently process the weight constrained reachability query on large scale data graphs in limited memory.Experiments show that this method can effectively reduce the index size through multiple datasets.

关 键 词：加权图 权值约束可达性查询 索引规模 

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