SC13 Home > SC13 Schedule > SC13 Presentation - Distributed Algorithms for Aligning Massive Networks

SCHEDULE: NOV 16-22, 2013

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.

Distributed Algorithms for Aligning Massive Networks

SESSION: ACM Student Research Competition Poster Reception

EVENT TYPE: ACM Student Research Competition Posters, ACM Student Research Competition

TIME: 5:15PM - 7:00PM

AUTHOR(S):Arif Khan

ROOM:Mile High Pre-Function

Given two graphs, the network alignment (NA) problem is to find the best one-to-one mapping between the vertices of one graph to those in the other by maximizing the number of overlapped edges. NA is an important problem with several applications in bioinformatics, computer vision and ontology matchings. It is an NP-hard problem, and solutions are heuristic and iterative in nature. Our algorithm is based on belief propagation and approximate weighted matching. Memory intensive requirements necessitate a distributed-memory implementation to solve large problems. A combination of sparse matrix operations and combinatorial algorithms makes network alignment a challenging problem. Our implementation is based on a special runtime system, Graph Multi-Threaded (GMT), designed to address irregular computation and memory accesses on distributed architectures. We demonstrate the utility of this approach by solving large problems that were previously not possible on shared-memory systems, and show strong scaling with 10x improvement on 64 nodes.

Chair/Author Details:

Arif Khan - Purdue University

Add to iCal  Click here to download .ics calendar file

Add to Outlook  Click here to download .vcs calendar file

Add to Google Calendarss  Click here to add event to your Google Calendar