Scalable Distance Labeling Maintenance and Construction for Dynamic Small-World Networks

Shortest path computation is a fundamental operation of many applications in small-world networks, and shortest path index has been extensively studied to achieve high query efficiency. However, small-world networks evolve continuously in real life, and their graph size expands rapidly, necessitating the investigation of efficient shortest path index maintenance and construction for large dynamic graphs. In this paper, we adopt the Core-Tree index, which has exceptional scalability while preserving high query efficiency, as the underlying shortest path index, and put forward efficient algorithms to maintain and construct it for large dynamic small-world networks. Specifically, we first propose update propagation mechanisms for our Dynamic Core-Tree (DCT) algorithm, based on which the global tree index strategy is designed for efficient query processing. Moreover, for the core index, we propose a Propagation-based Dynamic PLL incorporating coarse update and refined update phases to ensure correct and efficient index maintenance. To enhance update efficiency and scalability for the core index, we also propose novel Parallel Canonical 2-hop Labeling (PCL) and Batch PCL (BPCL) to efficiently generate minimal canonical labels and pruning point records. Experimental studies on large real-world datasets demonstrate the superiority of our methods over the state-of-the-art in terms of indexing, updating, and scalability.