Distributed Set Label-Constrained Reachability Queries over Billion-Scale Graphs
Yuanyuan Zeng, Wangdong Yang, Xu Zhou, Guoqing Xiao, Yunjun Gao, Kenli Li · 2022 IEEE 38th International Conference on Data Engineering (ICDE) · 2022
Set label-constrained reachability (SLCR) query in edge-labeled graphs is a building block of many graph-based applications. Formally, given two sets$S$and$T$of source and target vertices and a label set (, it returns all reachable vertex pairs (s, t) under the constraint of (, where$s$∊$S$and$t$∊T. There have been abundant index-based approaches to be applied to process the SLCR query. However, distributed approaches are desirable to process large-scale graphs because of the advantages of good scalability and real-time response. Now, there is no efficient distributed approach to the SLCR query. Most index-based approaches face limitations in terms of index construction and query performance when being extended to the distributed environment for processing large-scale graphs. To alleviate these problems, we first build a boundary graph-based index (BoundG) to reduce the time overhead of index construction. Consider the query performance of the BoundG-based approach has no noticeable improvement. We further construct a novel two layers 2-hop index (TL2hop), and a TL2hop-based query algorithm (TLQA) is designed by integrating an early termination strat-egy that reduces the communication overhead and boosts the query performance. Experimental results over eight data graphs demonstrate that the index time of BoundG is comparable to that of the state-of-the-art, and TL2hop significantly outperforms the state-of-the-art technique in terms of query response time (up to 4 orders of magnitude speedup).