Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Algorithms on billion-scale graph using 10GB RAM: I love DataFusion

semyonsinchenko.github.io

Post reply on HN
Print view View original

31–40 of 42 posts

Re: Algorithms on billion-scale graph using 10GB RAM: I love DataFusion

#31

Post by lmeyerov »

adsharma wrote: post #28
adsharma wrote: post #26

Earlier quoted context omitted.

I'm happy to credit these people. https://arrow.apache.org/docs/r/authors.html CUDA and the ecosystem around it is more complicated. I'll use it. I agree that it advanced the state of the art and helped fund some of the truly OSS projects. Don't feel the need to bring it up on a HN comment. Neither does the parent article by Sem. In fact, it's in the vendor's interest to transparently route the algorithms in Icebug t…

They use networkx today: https://github.com/rapidsai/nx-cugraph/ because it's more popular than networkit or icebug. But its popularity is based on ease of use, not performance: https://github.com/timlrx/graph-benchmarks Not clear if the author or anyone else has an updated version of these benchmarks. Opened an icebug issue on the repo.

see graph500

we use igraph cpu / cugraph gpu in pygraphistry/gfql projects, and our experience is cugraph is ~10X+ on tiny cheap GPUs over igraph. looking at that table, where all seem same magnitude as igraph, I'd therefore expect much better than all the options listed. And when things get bigger and it merits a bigger GPU, even better. The team has been doing a great job over the last decade, and all free.

Re: Algorithms on billion-scale graph using 10GB RAM: I love DataFusion

#32

Post by adsharma »

lmeyerov wrote: post #29
adsharma wrote: post #26

Earlier quoted context omitted.

I'm happy to credit these people. https://arrow.apache.org/docs/r/authors.html CUDA and the ecosystem around it is more complicated. I'll use it. I agree that it advanced the state of the art and helped fund some of the truly OSS projects. Don't feel the need to bring it up on a HN comment. Neither does the parent article by Sem. In fact, it's in the vendor's interest to transparently route the algorithms in Icebug t…

cudf+cugraph are the table+graph algorithms that started around that same time to align with it, that's what helped get arrow funded from the nvidia side can't reply on the below, but re:networkx, it was more of the reverse, they did a nice job of building a standalone embeddable table+graph arrow-friendly library over many years, and with networkx compatibility from the beginning. Later, they collaborated with the n…

The reason for not recommending networkx is the choice it offers:

  fast on the GPU: nx-cugraph
  slow on the CPU: networkx (no arrow, see linked graph-benchmark)
I'm looking to offer something that's best in class on both CPU and GPU, so people don't have to choose.

Now that nvidia is becoming a major CPU vendor, they may like the idea too.

Re: Algorithms on billion-scale graph using 10GB RAM: I love DataFusion

#33

Post by lmeyerov »

adsharma wrote: post #32
lmeyerov wrote: post #29

Earlier quoted context omitted.

cudf+cugraph are the table+graph algorithms that started around that same time to align with it, that's what helped get arrow funded from the nvidia side can't reply on the below, but re:networkx, it was more of the reverse, they did a nice job of building a standalone embeddable table+graph arrow-friendly library over many years, and with networkx compatibility from the beginning. Later, they collaborated with the n…

The reason for not recommending networkx is the choice it offers: fast on the GPU: nx-cugraph slow on the CPU: networkx (no arrow, see linked graph-benchmark) I'm looking to offer something that's best in class on both CPU and GPU, so people don't have to choose. Now that nvidia is becoming a major CPU vendor, they may like the idea too.

agreed. gfql already gives this best-of-both for oss cpu+gpu cypher as we've been steadily working through benchmarks like ldbc, pokec, etc.

The HPC lessons for graph algorithms is less obvious as the substrate the OP is working through is close but not quite what HPC folks figured out, so the trade-off of fast to write and maintainable (dataframe/db-based) vs at the achievable magnitude of performance is tricky. LLMs change the calculus here too IMO, so I've been thinking a lot about more NUMA-exposed ideas that before were relegated to PhD land.

Re: Algorithms on billion-scale graph using 10GB RAM: I love DataFusion

#34

Post by eeks »

danbruc wrote: post #12
chrisweekly wrote: post #3

> "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.

It reminds me of that Frank MacSherry paper[1]...

[1] "Scalability! But at what COST?"

Re: Algorithms on billion-scale graph using 10GB RAM: I love DataFusion

#35

Post by ssinchenko »

cpdomina wrote: post #14

cool! 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

Yes, my toy tool is similar by the concept to graphchi. But I did not write the vertex-centric processing from scratch and I'm relying on DataFusion built-ins (select, join, group by, aggregate)

Re: Algorithms on billion-scale graph using 10GB RAM: I love DataFusion

#36

Post by ssinchenko »

ratmice wrote: post #8

It would be nice if OP noted what caused the change in their opinion? did datafusion gain some feature that they noted was missing in the previous article, or did something in their understanding click so they could overcome the previous issues?

The previous issues were in my mind, not in DataFusion.

I tried using DataFusion as an in-memory tool, which was a mistake. If the graph fits in memory, Networkit, IGraph, etc. will almost always be faster. These tools cannot process anything bigger than the available memory.

So, I changed my approach. I wrote my own naive "disk checkpointer," offloading everything to disk and avoiding materialization. Although I was afraid that writing to and reading from the disk would be slow, it is surprisingly fast with DataFusion. The results are impressive: fast and out-of-core.

Sorry, this post is short and not very detailed. I did not expect it to be at the top of HN and receive so much attention.

Re: Algorithms on billion-scale graph using 10GB RAM: I love DataFusion

#37

Post by ssinchenko »

anon7725 wrote: post #7
chrisweekly wrote: post #3

> "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…

> 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.

Agreed, 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!

Re: Algorithms on billion-scale graph using 10GB RAM: I love DataFusion

#38

Post by ssinchenko »

nylonstrung wrote: post #27

Datafusion is undoubtedly one of the best open source projects of all time, it's so incredibly powerful and well designed. The extensibility is insane, you can create your own query language that compiles to logical plans.

I agree 100%! DataFusion is beautiful and easy to extend in any direction. For the second version of my "out-of-core" graph algorithms project, for example, I implemented my own "co-partitioning" to speed up joins and achieved a performance improvement of two times! It was also easy to modify the physical plan and declare partitioning.

Re: Algorithms on billion-scale graph using 10GB RAM: I love DataFusion

#40

Post by ssinchenko »

esafak wrote: post #4

Does it support out-of-core or multi-processor processing?

Yes, it is both out-of-core and multi-processor. I created this toy project to process graphs that cannot fit into memory (in CSR format) using all available cores.

The multi-processing relies on DataFusion's Tokyo workers. The out-of-core aspect is achieved through a combination of DataFusion FairSpillPool, Sort-Merge-Join, and manually offloading everything to temporary Parquet files on disk.

Post reply on HN