<inline-formula> <tex-math notation="LaTeX">$HT$ </tex-math></inline-formula>: A Novel Labeling Scheme for k-Hop Reachability Queries on DAGs

Abstract

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, namely HT, to accelerate $k$ -hop reachability queries answering. HT uses 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, HT uses a novel topological level to accelerate graph traversal. Further, we propose to enhance HT by two optimization techniques. The experimental results show that compared with the state-of-the-art approaches, HT works best for most graphs when answering $k$ -hop reachability queries with small index size and reasonable index construction time.

Keywords

• Graph data management
• reachability queries processing
• k-hop reachability%22%2C%22default_operator%22%3A%22AND%22%7D%7D%7D"> <italic xmlns:ali="http://www.niso.org/schemas/ali/1.0/" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance">k</italic>-hop reachability