News for hackers. Stuff that matters.
Re:On the Computational Complexity of MapReduce by chubot on Sunday October 05, 2014 @01:29PM (#8412815)
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

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.

Re:On the Computational Complexity of MapReduce by chillacy on Sunday October 05, 2014 @02:41PM (#8413025)
MR 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.
Re:On the Computational Complexity of MapReduce by TallGuyShort on Sunday October 05, 2014 @11:11PM (#8414161)
You 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/. It allows you to do graph processing in Spark, and I quite like its approach.
Re:On the Computational Complexity of MapReduce by ihodes on Sunday October 05, 2014 @08:17PM (#8413870)
Do you know of a group using Spark on petabytes (or even a terabyte(s)) of data?
Re:On the Computational Complexity of MapReduce by TallGuyShort on Sunday October 05, 2014 @11:17PM (#8414175)
The 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.
Re:On the Computational Complexity of MapReduce by rxin on Monday October 06, 2014 @01:15AM (#8414377)
There are several use cases that I know of. One public one is Taobao http://databricks.com/blog/2014/08/14/mining-graph-data-with...