Congratulations to Mr. Xiaocheng HU, Prof. Yufei TAO and Prof. Chin-Wan CHUNG (KAIST, Korea) won the Best Paper Award at ACM Conference on Management of Data (SIGMOD) 2013.
The annual SIGMOD conference is one of the most prestigious conferences in database research. It is a leading international forum for database researchers, practitioners, developers, and users to explore cutting-edge ideas and results, and to exchange techniques, tools, and experiences. The best paper award recognizes the highest quality paper at the conference.
Title: Massive Graph Triangulation
Abstract:
This paper studies I/O-efficient algorithms for settling the classic triangle listing problem, whose solution is a basic operator in dealing with many other graph problems. Specifically, given an undirected graph G, the objective of triangle listing is to find all the cliques involving 3 vertices in G. The problem has been well studied in internal memory, but remains an urgent difficult challenge when G does not fit in memory, rendering any algorithm to entail frequent I/O accesses. Although previous research has attempted to tackle the challenge, the state-of-the-art solutions rely on a set of crippling assumptions to guarantee good performance. Motivated by this, we develop a new algorithm that is provably I/O and CPU efficient at the same time, without making any assumption on the input G at all. The algorithm uses ideas drastically different from all the previous approaches, and outperformed the existing competitors by a factor over an order of magnitude in our extensive experimentation.
