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

Algorithm for solving interval coverage based on directed acyclic graph

给定一个有向无环图,回答可达性查询是图的基本操作之一。虽然很多方法使用树区间来加速可达查询的处理速度,但并不明确使用多少个区间比较合适。本文提出一种快速计算区间覆盖率的算法,该方法通过使用有效的剪枝策略来支持高效的覆盖率计算。基于所得到的区间覆盖率,可针对不同数据图确定合适的区间个数,以便在加速查询处理的同时,降低索引规模。基于多个真实数据集的实验验证了本文提出方法的高效性。

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.