CuckooGraph: A Scalable and Space-Time Efficient Data Structure for Large-Scale Dynamic Graphs

图在各种大数据应用中扮演着越来越重要的角色。然而，现有的图数据结构不能同时解决当前图动态更新、大规模和高查询复杂度所带来的性能瓶颈。本文提出了一种针对大规模动态图的新型数据结构——CuckooGraph。它不需要事先知道图数据的数量，并且可以根据数据规模自适应地调整为最节省内存的形式，从而更快地实现多个图分析任务。CuckooGraph的关键技术包括转换和拒绝列表。转换通过设计相关的数据结构，充分利用有限的内存，允许灵活的空间转换，以平滑地扩展/缩小所需的空间，具有更快的处理速度。拒绝列表有效地处理插入失败的项，并进一步提高了处理速度。我们进行了大量实验，结果表明，与现有技术相比，CuckooGraph在1跳继承者和前驱查询方面将查询时间显著缩短了四个数量级。

提出一种名为CuckooGraph的新型数据结构，旨在解决大规模动态图中的性能瓶颈问题，如何同时应对动态更新、大规模和高查询复杂度？

CuckooGraph利用TRANSFORMATION和DENYLIST两种关键技术，实现了自适应内存分配和高效的插入失败处理，从而在1-hop后继和前驱查询等任务中显著提高查询效率。

论文使用了广泛的实验验证了CuckooGraph的性能，实验结果表明CuckooGraph相较于现有的图数据结构在查询时间上提高了4个数量级。此外，论文还提供了开源代码，为后续相关研究提供了便利。

在相关研究方面，文中列举了一些现有的图数据结构，如CSR、CSC、COO等，以及一些动态图算法，如DAGuE、GraphChi等。