SC14 New Orleans, LA

The International Conference for High Performance Computing, Networking, Storage and Analysis

Computing Approximate b-Matchings in Large Graphs and an Application to k-Anonymity.


Student: Arif Khan (Purdue University)
Supervisor: Alex Pothen (Purdue University)

Abstract: Given a graph, b-Matching problem is to an edge weighted matching with maximum weight with constraint that every vertex v can match with at most a specified number of b vertices. It has been shown that b-Matching is useful in various machine learning problems such as classification, spectral clustering, graph sparsification, graph embedding and data privacy. The exact algorithms for this problem have high time as well as storage requirements, are inherently sequential, and therefore, are not practical solving large problems. We propose a 1/2-approximation algorithm which runs in linear time in the number of edges and also requires less storage. We show that our algorithm can solve large problems and can get up to 96% of the optimal solution. We also show that our algorithm scales up to 10x on 16 cores of Intel Xeon machines and up to 50x on 60 cores of Intel Xeon Phi machines.

Poster: pdf
Two-page extended abstract: pdf


Poster Index