search

anilpacaci / streaming-graph-partitioning

Experimental Setup for Performance Analysis of Streaming Algorithms
Apache License 2.0
30 stars 4 forks source link

METIS Partitioning on LDBC SNB Social Network #10

Open anilpacaci opened 7 years ago

anilpacaci commented 7 years ago

For streaming partitioning experiments, we need two baseline methods. First one is the de-facto hash partitioning, which is expected to perform worse. The other one is the golden standard partitioning method, METIS. Fortunately METIS is available as a software package. We need to transform our graph into METIS compatible format.

anilpacaci commented 7 years ago

So I was reading METIS partitioner documentation and it is actually quite simple to use. Biggest issue using the METIS partitioner is to convert our social network into METIS compatible format. METIS assumes a undirected graph model in adjacency list format. So the fist line (line 0) of the input file is going to be two integers, # of vertices and # of edges

METIS assumes that vertices have ids numbered from 1 to # of vertices. So we won't be able to use ids in our network. We need to create mapping from LDBC SNB ID to range of integers, but this is trivial. Input format that we need to convert requires separate line for each vertex where ith line represent the all neighbours of vertex i :

n_1 n_2 n_3 n_4

neighbour list does not have to be ordered by id (line number in this case).