K-step Reachability Query Algorithm for Large Graphs
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 que-ries.The paper conducts experimental tests based on 19 real datasets and compares with existing algorithms in three metrics:in-dex size,index time,and query time.The experimental results verify the efficiency of the proposed algorithm in this paper.
NETL
NSTL
万方数据
