EDTC：在GPU上针对动态图进行精确的三角形计数

《IEEE Transactions on Parallel and Distributed Systems》：EDTC: Exact Triangle Counting for Dynamic Graphs on GPU

动态图三角形计数面临内存与效率双重挑战，本文提出EDTC系统通过压缩哈希表、动态共享内存分配和GPU局部子图计算（UA-CSR结构）实现高效处理。

　　

摘要：

在更新动态图的过程中，对一条边的修改可能会导致多个三角形的添加或删除，而对多条边的修改可能只会导致一个三角形的添加或删除。因此，准确计算动态图中的三角形数量是一项具有挑战性的任务。由于动态图会不断更新，GPU的内存可能不足以存储较大的图。当这个不断增长的图无法被存储时，就会出现问题。基于哈希和二分搜索的三角形计数算法被认为是处理静态图最有效的方法。然而，当遇到度数较高的顶点时，基于哈希的三角形计数方法会因传统的哈希表构建方式而导致大量内存浪费，从而引发内存不足的问题。这个问题至今仍未得到解决。本文提出了一种针对动态图的三角形计数系统EDTC，同时确保了计数的准确性。该系统解决了三个主要问题：（1）引入了一种高效的EHTC算法，可以快速准确地计算图中的三角形数量；（2）引入了更新激活CSR（UA-CSR）的概念，并设计了一种数据结构来辅助其实现，该结构仅将受更新边影响的子图部分加载到GPU中，从而仅对该特定子图进行计算；（3）设计了一种压缩哈希表以减少内存消耗，并采用动态共享内存分配（DSA）策略来充分利用GPU的共享内存。