vasia / gelly-partition-centric Goto Github PK
View Code? Open in Web Editor NEWPartition-centric iterations for Gelly (EMDC ID2219 course project)
License: Apache License 2.0
Partition-centric iterations for Gelly (EMDC ID2219 course project)
License: Apache License 2.0
Hi Vasia,
Sky3 is down again. Can you tell someone to check it on Monday ?
Thanks.
Hi Vasia,
Can you get us a Flink cluster for performance testing ?
Best,
Kien
For the in-partition connected components algorithm, you can experiment with the following approaches:
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.
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:
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
Component id | Vertices |
---|---|
3 | 3, 5 |
edge (3, 4) => add 4 to the component
Component id | Vertices |
---|---|
3 | 3, 5, 4 |
edge (1, 3) => add 1 to the component and update the component Id to min(1, 3)=1
Component id | Vertices |
---|---|
1 | 3, 5, 4, 1 |
edge (2, 4) => add 2 to the component
Component id | Vertices |
---|---|
1 | 3, 5, 4, 1, 2 |
edge (5, 1) => both vertices already in the component
Component id | Vertices |
---|---|
1 | 3, 5, 4, 1, 2 |
edge (6, 7) => create new component with Id=6 and add both vertices
Component id | Vertices |
---|---|
1 | 3, 5, 4, 1, 2 |
6 | 6, 7 |
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.
Component id | Vertices |
---|---|
1 | 3, 5, 4, 1, 2, 6, 7 |
Based on today's meeting, we need to:
Please add anything I might have forgotten :)
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.