Efficient Maintenance of 2-Hop Labeling Index on Dynamic Small-World Graphs

Download PDF

Abstract

2-hop labeling has been widely utilized to accelerate the efficiency of online shortest distance queries. Given the nature of frequent changes in real-world graphs, the efficient maintenance of 2-hop labeling index has been extensively studied recently. However, existing methods cannot efficiently process large-scale graphs due to their high time and memory costs, and most of them process large batches of updates sequentially, significantly decreasing efficiency. In this paper, we propose a novel algorithm for maintaining the 2-hop labeling index in a parallel manner, called M2HL , which can efficiently handle both edge insertions and deletions. Moreover, we theoretically prove that M2HL maintains both correctness and minimality for the updated 2-hop labeling index. Our experiments on ten large-scale graphs demonstrate that M2HL outperforms the state-of-the-art 2-hop labeling maintenance methods by up to four orders of magnitude in speed while maintaining correctness and minimality, as well as exhibiting strong scalability and low memory usage.