图计算作为大数据处理的关键技术，在社交网络、金融、知识图谱等领域发挥重要作用。然而，动态图的网络结构随时间持续变化，静态图算法难以实时更新，且现有动态图方法在准确性与性能之间难以兼顾。研究团队聚焦动态图数据挖掘问题，以精确计数为目标，针对GPU架构设计新的动态图算法，实现了最先进的精确动态图挖掘系统。
研究团队首次提出了一种名为UA-CSR的新型数据结构，基于更新边对动态图进行增量计算，结合压缩哈希表与动态共享内存技术，有效解决了单GPU在处理大规模动态图时内存耗尽的瓶颈问题，显著提升了三角计数的效率。该方法在子图匹配领域具有可推广性，并针对高clique的情况进行了扩展，与最先进的k-clique计数系统做了对比，依旧保持性能优势。全面评估的实验结果表明，面对不同规模与不同结构的图数据均能保持性能优越性，展现出良好的可扩展性，并在保证精确计数的前提下，有效降低了存储占用和计算开销。
相关结果以“EDTC：Exact triangle counting for dynamic graphs on GPU”为题发表在《IEEE Transactions on Parallel and Distributed Systems》（JCR Q1，IF 6，CCF A）期刊上。该系列研究得到国家自然科学基金（62062059，62462052）、CCF-蚂蚁基金绿色计算专项、青海省重点研发计划（2023-QY-208）的资助。
供稿：计算机技术与应用学院
【编辑：赵浩威 责任编辑：金萍】