基于有向无环图的区间覆盖率求解算法  

Algorithm for solving interval coverage based on directed acyclic graph

作　　者：杜明[1] 庞建成 周军锋 DU Ming;PANG Jiancheng;ZHOU Junfeng(School of Computer Science and Technology,Donghua University,Shanghai 201620,China)

机构地区：[1]东华大学计算机科学与技术学院,上海201620

出　　处：《智能计算机与应用》2021年第2期23-28,34,共7页Intelligent Computer and Applications

基　　金：国家重点研发计划(2017YFB0309800)。

摘　　要：给定一个有向无环图,回答可达性查询是图的基本操作之一。虽然很多方法使用树区间来加速可达查询的处理速度,但并不明确使用多少个区间比较合适。本文提出一种快速计算区间覆盖率的算法,该方法通过使用有效的剪枝策略来支持高效的覆盖率计算。基于所得到的区间覆盖率,可针对不同数据图确定合适的区间个数,以便在加速查询处理的同时,降低索引规模。基于多个真实数据集的实验验证了本文提出方法的高效性。Given a directed acyclic graph,answering the reachability query is one of the basic operations of the graph.Although many methods use tree intervals to speed up the processing speed of reachable queries,it is not clear how many intervals are appropriate.This paper proposes an algorithm to quickly calculate the coverage of multiple intervals.This method supports efficient coverage calculation by using an effective pruning strategy.Based on the obtained interval coverage,an appropriate number of intervals can be determined for different data graphs,so as to reduce the index scale while speeding up query processing.Experiments based on multiple real data sets verify the efficiency of the method proposed in this paper.

关 键 词：有向无环图 可达性查询处理 区间覆盖率 

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