4 ms·
So they are talking about how many MapReduce rounds it takes to express certain graph algorithms. (A single MapReduce round is of course O(n log n) with respec
by chubot 12y ago
So they are talking about how many MapReduce rounds it takes to express certain graph algorithms. (A single MapReduce round is of course O(n log n) with respect to the number of records.)
I wonder if this context is practical/realistic. One paper I thought was interesting is GraphChi, a graph processing framework that runs on a single machine:
http://graphlab.org/projects/graphchi.html http://graphlab.org/projects/graphchi.html
Graphs can be encoded very efficiently; you need a pair of integer IDs for a pair of nodes, and maybe a weight or some other small payload data. A graph of say 7 billion nodes for everyone in the world will often fit in memory on a single machine these days, depending on the number of edges. GraphChi uses disk, so you have even more space, if you are willing to constrain the model (MapReduce is of course already heavily constrained, especially for graphs).
The raw source data is probably larger than a machine, but you could just run a MapReduce to copy it out into a bunch of (ID, ID) pairs, do your hairy graph algorithms on a single machine, then export the result back your data store with a MapReduce join.
You could use either something like GraphChi or just an arbitrary C/Java program working on a big graph in memory.
My hunch is that this is a lot more tractable that sequential MapReduce... I'd be interested in hearing if people have big graph problems where you couldn't use such an approach.
- chillacy 12y agoMR is a pretty inflexible paradigm, and doesn't really suit graph problems well at all. Most people I know prefer to use Spark (or in the case of graph problems, giraph). Of course this is for huge graphs that won't fit on a machine (petabytes). If it fits on a machine it's far easier to not muck around with distributed computing.
- ihodes 12y agoDo you know of a group using Spark on petabytes (or even a terabyte(s)) of data?
- TallGuyShort 12y agoThe scalability of Spark is certainly not as established as that of Hadoop. It's entirely anecdotal as I'm not in a position to share verifiable details, but I know of several installations that run Spark on several-hundred-node clusters. They're certainly well into terabytes, if not in the neighborhood of petabytes.
- rxin 12y agoThere are several use cases that I know of. One public one is Taobao http://databricks.com/blog/2014/08/14/mining-graph-data-with-spark-at-alibaba-taobao.html http://databricks.com/blog/2014/08/14/mining-graph-data-with...
- TallGuyShort 12y agoYou may be interested in GraphX, which describes itself as a hybrid between the "data-parallel" approach of MapReduce and core Spark, and the "graph-parallel" approach of Giraph, Graphlab, etc. See http://spark.apache.org/graphx/ http://spark.apache.org/graphx/. It allows you to do graph processing in Spark, and I quite like its approach.