4 ms·
> "I can compute PageRank on a directed graph with one billion edges (graph500-26 from the Graphalytics dataset) using 5 GB of memory. Alternatively, I can iden
by chrisweekly 2mo ago
> "I can compute PageRank on a directed graph with one billion edges (graph500-26 from the Graphalytics dataset) using 5 GB of memory. Alternatively, I can identify all the weakly connected components in a graph with two billion edges (twitter_mpi from the same dataset collection) using 10 GB of memory. Neither NetworkX nor Igraph can do this; most existing graph algorithms require the graph to fit into memory. Previously, I thought you needed Apache Spark and GraphFrames for billion-scale graph analytics. Now, however, I think all you need is a laptop. I have completely changed my old opinion about using Apache DataFusion for graph analytics."
Impressive!
- anon7725 2mo ago> most existing graph algorithms require the graph to fit into memory. You can get pretty far with sparse graphs, which are just arrays, in combination with memory mapping.
- ssinchenko 2mo agoAgreed, but I didn't see anything like this in popular projects such as Networkit or IGraph. If you have an example of an implementation, I would appreciate it!
- danbruc 2mo ago33M vertices and 1B edges easily fits into memory, if you use 32 bit integers, it will require about 4 GiB of memory. Out of curiosity I just implemented generating a random graph of that size and calculating one page rank iteration on it in the most naive way (20 lines of C#) and it consumed 8.4 GiB of memory and got one iteration done in 4:20 minutes single threaded.
- eeks 2mo agoIt reminds me of that Frank MacSherry paper[1]... [1] "Scalability! But at what COST?"