SCHEDULE: NOV 16-21, 2014

When viewing the Technical Program schedule, on the far righthand side is a column labeled "PLANNER." Use this planner to build your own schedule. Once you select an event and want to add it to your personal schedule, just click on the calendar icon of your choice (outlook calendar, ical calendar or google calendar) and that event will be stored there. As you select events in this manner, you will have your own schedule to guide you through the week.

ENTIRE WEEK SUNDAY MONDAY TUESDAY WEDNESDAY THURSDAY FRIDAY

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

SESSION: ACM Student Research Competition Poster Reception

EVENT TYPE: ACM Student Research Competition

TIME: 5:15PM - 7:00PM

AUTHOR(S):Arif Khan

ROOM:New Orleans Theater Lobby

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.