Skip to main content
eScholarship
Open Access Publications from the University of California

College of Engineering

Electrical & Computer Engineering bannerUC Davis

Dynamic Graphs on the GPU

  • Author(s): Awad, Muhammad A.;
  • Ashkiani, Saman;
  • Porumbescu, Serban D.;
  • Owens, John D.
  • et al.
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.

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View