Really cool visualization, amazing how it resembles a neural network.
I'm pretty sure that's some stock output from CAIDA, looks like a traceroute graph from the inset
Algorithms on billion-scale graph using 10GB RAM: I love DataFusion
11–20 of 42 posts
Re: Algorithms on billion-scale graph using 10GB RAM: I love DataFusion
#12> "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. Previ…
33M 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.
Re: Algorithms on billion-scale graph using 10GB RAM: I love DataFusion
#13Related, we recently release the polars version of GFQL, the only oss cypher property graph query engine for CPU+GPU, and even better, no database nor outside process needed. We started doing LDBC benchmarks vs neo4j, memgraph, kuzu, etc, and are already starting to outperform them both on latency for small OLTP graph searches and $, speed for big graph OLAP ones, especially in GPU mode.
The cool in the original post was directly inspired by our work here, with our advocacy to the author of keeping their previous Spark work for initial data lake data extraction, and the actual graph work to be redone in our columnar in-memory optimized style for magnitudes of speedup , cost savings
Pip install, benchmarks : https://pygraphistry.readthedocs.io/en/latest/gfql/benchmark...
Re: Algorithms on billion-scale graph using 10GB RAM: I love DataFusion
#14cool! you might be interested in graphchi (2012), also designed to do large scale graph operations on a single machine
Re: Algorithms on billion-scale graph using 10GB RAM: I love DataFusion
#15The idea of graph algorithms on Apache arrow at scale originated here. 100+ graph algorithms running on columnar memory.
https://github.com/Ladybug-Memory/icebug
Out of core with datafusion is the main innovation here in graphframes-rs. But it has only 2 algorithms so far.
Icebug and LadybugDB can be tightly integrated to efficiently move tables encoded as compressed sparse row (CSR) into arrow memory.
Jupyter notebooks available.
Re: Algorithms on billion-scale graph using 10GB RAM: I love DataFusion
#16It's hard to take the article seriously when it has quotes like this:
"The hardest part. 2B edges twitter graph is already huge (its edges are 30 GB in CSV !!!)."
Who cares how big the graph is in CSV? That's not the representation you operate over in big data.
All of this would have easily fit in memory on any reasonable modern system.
Re: Algorithms on billion-scale graph using 10GB RAM: I love DataFusion
#17The idea of graph algorithms on Apache arrow at scale originated here. 100+ graph algorithms running on columnar memory. https://github.com/Ladybug-Memory/icebug Out of core with datafusion is the main innovation here in graphframes-rs. But it has only 2 algorithms so far. Icebug and LadybugDB can be tightly integrated to efficiently move tables encoded as compressed sparse row (CSR) into arrow memory. Jupyter notebo…
https://github.com/LadybugDB/ladybug-icebug-notebooks/blob/m...
Trade-off: datafusion allows you to do fine grained storage integration (spill to disk as a part of the algorithm).
The icebug/ladybug way is coarse grained. But it allows you to run cypher instead of writing datafusion operators.
Re: Algorithms on billion-scale graph using 10GB RAM: I love DataFusion
#18It's hard to take the article seriously when it has quotes like this: "The hardest part. 2B edges twitter graph is already huge (its edges are 30 GB in CSV !!!)." Who cares how big the graph is in CSV? That's not the representation you operate over in big data. All of this would have easily fit in memory on any reasonable modern system.
Here is a proposal built on parquet/arrow. What other alternatives exist that can be queried by a database without ingest?
Re: Algorithms on billion-scale graph using 10GB RAM: I love DataFusion
#19cool! you might be interested in graphchi (2012), also designed to do large scale graph operations on a single machine https://github.com/GraphChi/graphchi-cpp#performance
It looks similar to networkit in that it represents graphs using row oriented memory layout.
I forked networkit for exactly this reason. Columnar memory is much more efficient.
Re: Algorithms on billion-scale graph using 10GB RAM: I love DataFusion
#20Love this Sem. Will provide a great alternative to the SQL based connected components algorithm we ship in Splink. Looking forward to testing how much faster it is. Thanks for your work on it!