开发者 Semyon Sinchenko 利用 Apache DataFusion 实现了一套 Map-Reduce 图计算框架，突破了传统图算法库的内存限制，在仅 10GB 内存约束下成功处理十亿级规模的图数据。1 该方案通过将数据溢出到磁盘、采用面向批量扫描而非随机访问的算法设计，实现了在极限资源条件下的大规模图处理。1
在 PageRank 算法测试中，使用图 500-26 数据集（包含 10 亿条有向边），仅耗用 5GB 内存，完成 15 次迭代用时约 30 分钟。1 弱连通分量（WCC）识别任务处理了 twitter_mpi 数据集，该数据集包含 20 亿条边（CSV 格式原始大小 30GB），使用 10GB 内存在 22 次迭代内完成计算。1 图对称化后，WCC 前处理阶段边数增至 32.28 亿条，但首次迭代后又降至 8.4 亿条。1
NetworkX 和 Igraph 等现有图算法库无法处理这一规模的数据，通常需要借助 Apache Spark 和 GraphFrames 等分布式框架。1 本方案的计算结果与 Graphalytics 提供的基准真值实现了 100% 匹配，验证了其精度和可靠性。1
A developer has successfully implemented graph computing algorithms capable of processing billions of edges within severe memory constraints by leveraging Apache DataFusion.1 The work demonstrates that large-scale graph analysis previously thought to require distributed systems like Apache Spark can be accomplished on a single machine with careful algorithm design.
The developer implemented a Map-Reduce framework for graph computation that spills data to disk and employs batch-scan-optimized algorithms rather than random-access approaches.1 Using the graph500-26 dataset containing 1 billion directed edges, the PageRank algorithm completed 15 iterations in approximately 30 minutes while consuming just 5GB of memory.1 In a more demanding test, the weakly connected components (WCC) algorithm processed the twitter_mpi dataset of 2 billion edges—stored as a 30GB CSV file—using 10GB of memory, with 22 iterations required for convergence.1 The WCC computation involved preprocessing that expanded the edge count to 3.228 billion edges due to graph symmetrization, which then decreased to 840 million edges after the first iteration.1
Traditional graph libraries such as NetworkX and Igraph cannot handle graphs at these scales, and practitioners typically resort to Apache Spark with GraphFrames for such workloads.1 The results achieved validation against benchmark ground truth provided by Graphalytics with 100% accuracy.1
评论
还没有评论，欢迎留下第一条。