$HT$ : A Novel Labeling Scheme for k-Hop Reachability Queries on DAGs
Ming Du, Yang Anping, Junfeng Zhou, Xian Tang, Ziyang Chen, Yanfei Zuo · IEEE Access · 2019
Given a directed acyclic graph (DAG), a$k$-hop reachability query${u}\xrightarrow {?k}{v}$is used to answer whether there exists a path from$u$to$v$with length$\leq k$. Answering$k$-hop reachability queries is a fundamental graph operation and has been extensively studied during the past years. Considering that existing approaches still suffer from inefficiency in practice when processing large graphs, we propose a novel labeling scheme, namelyHT, to accelerate$k$-hop reachability queries answering.HTuses a constrained 2hop distance label to maintain the length of shortest paths between a set of hop nodes and other nodes, and for the remaining reachability information,HTuses a novel topological level to accelerate graph traversal. Further, we propose to enhanceHTby two optimization techniques. The experimental results show that compared with the state-of-the-art approaches,HTworks best for most graphs when answering$k$-hop reachability queries with small index size and reasonable index construction time.