CS PhD Student Takes 3rd Place at Supercomputing Conference
12-03-2014
Writer(s): Jesica E. Hollinger
CS PhD student Ariful Khan earned third place at the Supercomputing 2014 Conference (SC14) – one of the top-tier international conferences for high performance computing in New Orleans, Louisiana.
Ariful earned his placement at the ACM Student Research Competition for his research, “Computing Approximate b-Matches in Large Graphs and an Application to k-Anonymity”.
A significant achievement in the graduate category, Arif competed against 144 submissions, with only 23 selected to attend the conference. Those selected were judged in an open poster session, then five finalists were asked to give short presentations for the judges to evaluate their research.
Ariful explained his research designed an approximation algorithm named bSuitor, designed to find maximum weighted b-Matchings on a graph.
“It is based on the concept of a proposal-rejection scheme. So far, it is the only parallel approximation algorithm for this problem. bSuitor shows very good scalability on both Intel Xeon and Xeon-Phi architectures. It also outperforms other competing algorithms for this problem on a serial machine,” Arif said. “We applied bSuitor to solve an important data privacy problem named k-Anonymity and showed that with bSuitor the k-Anonymity problem can be solved at least 100 times faster than the current state of the art,” he added.
He also explained that the most important contribution of the research is that the bSuitor reduces the overall space complexity of the k-Anonymity problem from O(n^2) to O(n) (where n is the number of individuals) which enabled them to solve very large problems which could not be solved before.
Ariful credits his success to his advisor, Professor Alex Pothen, for his expert knowledge of Graph Algorithms and Combinatorial Scientific Computing, which guided him to successfully conduct the research.
“Professor Pothen is instrumental not only in this particular research but also advising me towards my doctoral degree,” Ariful said. He introduced the b-Matching problem to me and pointed out that the k-Anonymity problem that can be solved efficiently by our bSuitor algorithm,” he added.
For more than twenty years, the SC has been a venue for solving some of the world’s hardest problems. The conference is packed with technical sessions, tutorials, workshops, and posters. More than 10,000 individuals attended this year's conference, including scientists, engineers, researchers, educators, students, programmers, system administrators, and developers.
First place was awarded to Amanda Bienz, University of Illinois at Urbana-Champaign, and second place to Gagan Gupta, University of Wisconsin, Madison.