Hornet: Efficient Data Structure for Dynamic Sparse Graphs and Matrices on GPUs [pdf] (davidbader.net)

Researchers introduced Hornet, a new GPU-oriented data structure for dynamic sparse graphs and matrices that supports fast, large-scale updates without global reallocation or reinitialization. Hornet is platform-independent but implemented and experimentally validated on GPUs; it claims much faster initialization (3.5×–26× vs. cuSTINGER), update rates exceeding 200M updates/sec, and substantially lower memory use (a small fraction of AIM’s needs, ~5–10× less than cuSTINGER). Compared with static formats, Hornet needs only 5–35% extra memory over CSR and on average ~30% less than COO, while guaranteeing a provable worst-case memory upper bound of 2·|E| and a practical average close to 1.4·|E|. Technically, Hornet uses a hierarchical layout: per-vertex adjacency lists are stored inside blocks grouped into block-arrays; each vertex’s block size is the smallest power-of-two that fits its degree, and block-array counts are powers-of-two to bound wasted space. Allocation and reclamation use a vectorized bit-tree (Vec-Tree) per block-array — a boolean OR tree that finds empty blocks in O(log |BA|) — while B+trees manage block-array metadata. This design yields constant-time (amortized) insert/delete semantics without fragmented allocations and enables efficient, high-throughput dynamic graph algorithms on GPUs, addressing locality and irregularity challenges that hamper traditional sparse formats.