giraph-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Aapo Kyrola <akyr...@cs.cmu.edu>
Subject Re: k-way graph partitioning
Date Fri, 24 Aug 2012 12:45:42 GMT
Claudio,

do you know this tech-report from Microsoft about streaming graph partitioning:
http://research.microsoft.com/apps/pubs/default.aspx?id=155926

The partitioning quality is not of course as good as with Metis, but much much faster
and more  feasible (Metis requires huge amount of memory on big graphs)..

Aapo Kyrola
Ph.D. student, http://www.cs.cmu.edu/~akyrola
GraphChi: Big Data - small machine: http://graphchi.org


On Aug 24, 2012, at 8:31 AM, Claudio Martella wrote:

> Hello list,
> 
> I'm looking for a nice k-way graph partitioning algorithm (where with
> nice I mean that fits easily to the pregel paradigm). The pregel paper
> has a semi-clustering algorithm with a maxClusters parameter. My
> understanding of this algorithms is that it requires quite a lot of
> data to flow around the vertices, as each vertex may pass around the
> clusters (which consist of the list of vertices belonging to them)
> etc. It looks quite I/O expensive to me.





Mime
View raw message