vasia / gelly-partition-centric Goto Github PK

Hi Vasia,
Sky3 is down again. Can you tell someone to check it on Monday ?
Thanks.

For the in-partition connected components algorithm, you can experiment with the following approaches:

1. Store the whole partition as a graph structure (adjacency list / matrix) and find connected components using BFS/DFS iteratively for each vertex. This is the approach used in the Giraph++ paper.

2. Use a semi-streaming-like graph algorithm. In this model, your partition operator will iterate over "augmented" edges, where the edge source vertex has an associated value (the component Id). You can create this type of records with a join of your workset (vertices) and edges. The algorithm works as follows:

• For each partition, you maintain a disjoint set data structure for the partitions' components. For each edge, check if its endpoints already belong to an existing component. If not, create a component with id the smallest of the vertex Ids. If they belong to different components, merge them and update the component Id to the smallest of the 2 components Ids. If only one of the endpoints belongs to a component, add the other one to the same component and update the component Id if necessary.

Consider the following edges input in a partition: (3, 5), (3, 4), (1, 3), (2, 4), (5, 1), (6, 7), (5, 6). The algorithm proceeds as follows (assume each vertex has its own Id as initial component Id):

edge (3, 5) => create a new component and add the vertices

edge (3, 4) => add 4 to the component

edge (1, 3) => add 1 to the component and update the component Id to min(1, 3)=1

edge (2, 4) => add 2 to the component

edge (5, 1) => both vertices already in the component

edge (6, 7) => create new component with Id=6 and add both vertices

edge (5, 6) => 5 belongs to comp=1, 6 belongs to comp=6 => merge the components and update the component Id to min(1, 6)=1.

The current plan implementation can be simplified. One option would be to implement it like in this figure:

http://snap.stanford.edu/data/index.html
http://konect.uni-koblenz.de/networks/

Hi Vasia,

Can you get us a Flink cluster for performance testing ?

Best,
Kien

Based on today's meeting, we need to:

• measure total time for job execution only
• measure time per iteration
• measure messages sent per iteration
• measure active vertices per iteration
• implement one more algorithm, e.g. SSSP

Please add anything I might have forgotten :)