BatchHL+: batch dynamic labelling for distance queries on large-scale networks

Simple item page
dc.citation.issue1
dc.citation.volume33
dc.contributor.authorFarhan M
dc.contributor.authorKoehler H
dc.contributor.authorWang Q
dc.date.accessioned2024-11-21T01:32:47Z
dc.date.available2024-11-21T01:32:47Z
dc.date.issued2024-01
dc.description.abstractMany real-world applications operate on dynamic graphs to perform important tasks. In this article, we study batch-dynamic algorithms that are capable of updating distance labelling efficiently in order to reflect the effects of rapid changes on such graphs. To explore the full pruning potentials, we first characterize the minimal set of vertices being affected by batch updates. Then, we reveal patterns of interactions among different updates (edge insertions and edge deletions) and leverage them to design pruning rules for reducing update search space. These interesting findings lead us to developing a new batch-dynamic method, called BatchHL+ , which can dynamize labelling for distance queries much more efficiently than existing work. We provide formal proofs for the correctness and minimality of BatchHL+ which are non-trivial and require a delicate analysis of patterns of interactions. Empirically, we have evaluated the performance of BatchHL+ on 15 real-world networks. The results show that BatchHL+ significantly outperforms the state-of-the-art methods with up to 3 orders of magnitude faster in reflecting updates of rapidly changing graphs for distance queries.
dc.description.confidentialfalse
dc.edition.editionJanuary 2024
dc.format.pagination101-129
dc.identifier.citationFarhan M, Koehler H, Wang Q. (2024). BatchHL <sup>+</sup> : batch dynamic labelling for distance queries on large-scale networks. VLDB Journal. 33. 1. (pp. 101-129).
dc.identifier.doi10.1007/s00778-023-00799-9
dc.identifier.eissn0949-877X
dc.identifier.elements-typejournal-article
dc.identifier.issn1066-8888
dc.identifier.pii00778-023-00799-9
dc.identifier.urihttps://mro.massey.ac.nz/handle/10179/72046
dc.languageEnglish
dc.publisherSpringer-Verlag GmbH Germany, part of Springer Nature
dc.publisher.urihttps://link.springer.com/article/10.1007/s00778-023-00799-9
dc.relation.isPartOfVLDB Journal
dc.rights(c) 2023 The Author/s
dc.rightsCC BY 4.0
dc.rights.urihttps://creativecommons.org/licenses/by/4.0/
dc.subjectShortest-path distance
dc.subjectBatch-dynamic graphs
dc.subject2-Hop cover
dc.subjectHigh-way cover
dc.subjectDistance labelling maintenance
dc.subjectGraph algorithms
dc.titleBatchHL+: batch dynamic labelling for distance queries on large-scale networks
dc.typeJournal article
pubs.elements-id462367
pubs.organisational-groupOther
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Published version.pdf
Size:
1.51 MB
Format:
Adobe Portable Document Format
Description:
462367 PDF.pdf
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
9.22 KB
Format:
Plain Text
Description:
Download
Collections
Journal Articles