A Parallel Framework for Efficiently Updating Graph Properties in Large Dynamic Networks
Abstract
Graph queries on large networks leverage the stored graph properties to provide faster results. Since real-world graphs are mostly dynamic, i.e., the graph topology changes over time, the corresponding graph attributes also change over time. In certain situations, recompiling or updating earlier properties is necessary to maintain the accuracy of a response to a graph query. Here, we first propose a generic framework for developing parallel algorithms to update graph properties on large dynamic networks. We use our framework to develop algorithms for updating Single Source Shortest Path (SSSP) and Vertex Color. Then we propose applications of the developed algorithms in Unmanned Aerial Vehicle (UAV) based delivery systems under time-varying dynamics. Finally, we implement our SSSP and vertex color update algorithms for Nvidia GPU architecture and show empirically that the developed algorithms can update properties in large dynamic networks faster than the state-of-the-art techniques.
Recommended Citation
A. Khanda and S. K. Das, "A Parallel Framework for Efficiently Updating Graph Properties in Large Dynamic Networks," ACM International Conference Proceeding Series, pp. 298 - 299, Association for Computing Machinery (ACM), Jan 2023.
The definitive version is available at https://doi.org/10.1145/3571306.3571359
Department(s)
Computer Science
Keywords and Phrases
Datasets; Gaze Detection; Neural Networks; Text Tagging
International Standard Book Number (ISBN)
978-145039796-4
Document Type
Article - Conference proceedings
Document Version
Citation
File Type
text
Language(s)
English
Rights
© 2023 Association for Computing Machinery, All rights reserved.
Publication Date
04 Jan 2023
Comments
National Science Foundation, Grant OAC-2104078