Fast fully dynamic labelling for distance queries

Muhammad Farhan*, Qing Wang, Yu Lin, Brendan McKay

*Corresponding author for this work

    Research output: Contribution to journalArticlepeer-review

    6 Citations (Scopus)

    Abstract

    Finding the shortest-path distance between an arbitrary pair of vertices is a fundamental problem in graph theory. A tremendous amount of research has explored this problem, most of which is limited to static graphs. Due to the dynamic nature of real-world networks, such as social networks or web graphs in which a link between two entities may fail or become alive at any time, there is a pressing need to address this problem for dynamic networks. Existing work can only accommodate distance queries over moderately large dynamic networks due to high space cost and long pre-processing time required for constructing distance labelling, and even on such moderately large dynamic networks, distance labelling can hardly be updated efficiently. In this article, we propose a fully dynamic labelling method to efficiently update distance labelling so as to answer distance queries over large dynamic graphs. At its core, our proposed method incorporates two building blocks: (i) incremental algorithm for handling incremental update operations, i.e. edge insertions, and (ii) decremental algorithm for handling decremental update operations, i.e. edge deletions. These building blocks are built in a highly scalable framework of distance query answering. We theoretically prove the correctness of our fully dynamic labelling method and its preservation of the minimality of labelling. We have also evaluated on 13 real-world large complex networks to empirically verify the efficiency, scalability and robustness of our method.

    Original languageEnglish
    Pages (from-to)483-506
    Number of pages24
    JournalVLDB Journal
    Volume31
    Issue number3
    DOIs
    Publication statusPublished - May 2022

    Fingerprint

    Dive into the research topics of 'Fast fully dynamic labelling for distance queries'. Together they form a unique fingerprint.

    Cite this