$HT$ : A Novel Labeling Scheme for k-Hop Reachability Queries on DAGs
Open Access
- 28 November 2019
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Access
- Vol. 7, 172110-172122
Abstract
Given a directed acyclic graph ( DAG), a k-hop reachability query u?kv is used to answer whether there exists a path from u to v with length ≤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
Funding Information
- National Basic Research Program of China (2017YFB0309800)
- National Natural Science Foundation of China (61472339, 61303040, 61572421, 61272124)
This publication has 22 references indexed in Scilit:
- Reachability queryingProceedings of the VLDB Endowment, 2014
- Reachability queries on large dynamic graphs2014
- Efficient processing of $k$ k -hop reachability queriesThe VLDB Journal, 2013
- Simple, fast, and scalable reachability oracleProceedings of the VLDB Endowment, 2013
- Fast exact shortest-path distance queries on large networks by pruned landmark labeling2013
- TF-Label2013
- FERRARI: Flexible and efficient reachability range assignment for graph indexing2013
- K-reachProceedings of the VLDB Endowment, 2012
- An improved algorithm for transitive closure on acyclic digraphsTheoretical Computer Science, 1988
- Depth-First Search and Linear Graph AlgorithmsSIAM Journal on Computing, 1972