一种适用于大图的k步可达性查询算法  

K-step Reachability Query Algorithm for Large Graphs

作　　者：同正南 卜天明[1] TONG Zhengnan;BU Tianming(School of software Engineering,East China Normal University,Shanghai 200062,China)

机构地区：[1]华东师范大学软件工程学院,上海200062

出　　处：《计算机科学》2024年第S01期651-660,共10页Computer Science

摘　　要：k步可达查询用于在给定的有向无环图(Directed Acyclic Graph,DAG)中回答两点之间是否存在长度不超过k的路径。针对现有方法的索引规模大、查询处理效率低的问题,提出了一种构建在大图上的基于树覆盖的倍增索引来提高索引查询效率,并结合GRAIL算法和改进的FELINE算法对本身就不可达查询点对进行剪枝。基于19个真实的数据集进行了实验测试,并将所提算法与现有算法在构建索引大小、索引时间、查询时间3个指标上进行了实验对比。实验结果验证了所提算法的高效性。The k-step reachable query is used to answer whether there exists a path of length not exceeding k between two points in agiven directed acyclic graph(DAG).To address the problems of large index size and low query processing efficiency of existing methods,this paper proposes a multiplicative index built on a large graph based on tree cover to improve index query efficiency,and combines GRAIL algorithm and the improved FELINE algorithm for pruning the point pairs of inherently unreachable queries.The paper conducts experimental tests based on 19 real datasets and compares with existing algorithms in three metrics:index size,index time,and query time.The experimental results verify the efficiency of the proposed algorithm in this paper.

关 键 词：k步可达性查询 倍增索引 索引标签 树覆盖 在线搜索 

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