10GB内存搞定十亿规模图算法！Apache DataFusion让图分析只需一台笔记本

测试设置测试了两项任务分别是PageRank和弱连通分量WCC。PageRank任务是在Graphalytics数据集的graph500 - 26上计算PageRank相关关键信息为节点数量32,804,978、边的数量1,051,922,853、有向性无向、内存限制5GB、DataFusion池大小4GB。基于DataFusion的实现采用经典Pregel算法通过连接和聚合操作实现与Spark的GraphFrames库核心实现相似。WCC任务是在同一数据集的twitter_mpi上识别所有弱连通分量关键信息为节点数量52,579,682、边的数量1,963,263,821、有向性有向、内存限制10GB、DataFusion池大小8GB。基于DataFusion的实现参考了Bögeholz等人的论文“数据库内连通分量分析”之前已为Spark的GraphFrames实现过相同算法。测试结果PageRank部分相对容易使用SMJ可证明其扩展性也可用哈希连接HJ因顶点少且PageRank状态简单HJ更快。算法基于有向边运行无需对图对称化将边和状态卸载到磁盘迭代至收敛。15次完整迭代约需30分钟测试重点是内存使用结果与真实值在0.0001误差范围内匹配还有优化空间。WCC是最具挑战性部分Twitter图庞大CSV格式边数据有30GB。WCC算法需对边对称化峰值时用8GB的DataFusion池处理近40亿条边迭代后收缩减少边数量算法10分钟完成且内存压力低结果正确可与Graphalytics提供的真实值核对。代码代码地址为。大部分代码自己编写无README部分注释可能过时项目中学习Rust和DataFusion核心部分未用大语言模型LLM辅助。图的表示方式与Spark的GraphFrames相似核心部分包括Pregel主循环和WCC实现。若想了解Pregel表示法[CME 323课程第八讲分布式算法与优化](https://web.stanford.edu/~rezab/classes/cme323/S15/notes/lec8.pdf)是有用参考资料。还给出了使用该API进行PageRank计算的示例代码。