Abstract: As an important data pre-processing operation,graph sparsification has attracted wide attentions from the area of database．Nowadays the graph data is becoming popular and scale．Thus this paper proposed an efficient parallel graph sparsification algorithm,namely the MR-GSpar algorithm．The MR-GSpar algorithm is presented by reforming the traditional Minhash algorithm into a parallel and distributed algorithm using MapReduce framework,which can archive efficient sparsification on large-scale graph data in a large machine cluster environment．Experiments on real datasets show that the algorithm is feasible and effective．

Key words: Graph sparsification,Minhsh,MapReduce framework,MR-GSpar algorithm