| Title | Dynamic Graphs on the GPU |
| Publication Type | Conference Paper |
| Year of Publication | 2020 |
| Authors | Awad, M. A., Ashkiani, S., Porumbescu, S. D., Owens, J. D. |
| Conference Name | 2020 IEEE International Parallel and Distributed Processing Symposium (IPDPS) |
| Keywords | adjacency lists, Arrays, data deletion, data structures, deletion speedups, dynamic, dynamic graph data structures, dynamic updates, Gold, GPU, graph, graph theory, graphics processing units, hash table, maintenance engineering, Memory management, privacy, pubcrawl, Scalability, Sparse matrices |
| Abstract | We present a fast dynamic graph data structure for the GPU. Our dynamic graph structure uses one hash table per vertex to store adjacency lists and achieves 3.4-14.8x faster insertion rates over the state of the art across a diverse set of large datasets, as well as deletion speedups up to 7.8x. The data structure supports queries and dynamic updates through both edge and vertex insertion and deletion. In addition, we define a comprehensive evaluation strategy based on operations, workloads, and applications that we believe better characterize and evaluate dynamic graph data structures. |
| DOI | 10.1109/IPDPS47924.2020.00081 |
| Citation Key | awad_dynamic_2020 |
Dynamic Graphs on the GPU