Communications of the ACM
Parallel Graph Analytics
Visualization of the routing paths of the Internet.
Credit: Barrett Lyon / The Opte Project
The study of graphs began in the 18th century with Euler's work on the "Bridges of Königsberg" problem, but it is only since the creation of the Web two decades ago that large-scale parallel computers have been used to study graph properties. Today, this field, known as "parallel graph analytics," touches all our lives, even if we are not aware of it. When we use a Web search engine or get a friend recommendation on Facebook, graph analytics is at work behind the scenes. Companies like Amazon and Netflix use parallel graph analytics to find patterns of purchases by their customers, enabling them to make targeted product recommendations. And intelligence agencies use parallel graph analytics to find key players, called "centralities," in terrorist networks.
Key Insights
Using computers to study graph properties is not new; 40 years ago, in 1976, mathematicians Kenneth Appel and Wolfgang Haken ran a FORTRAN program for 1,200 hours to prove the four-color theorem for planar graphs.a Today, we are interested in studying not only the mathematical properties of different kinds of graphs (such as planar graphs) but also in computing and exploiting properties of particular graphs that arise from big datasets. There are three main challenges in performing computations on these graphs—large graph sizes, diversity in graph structure, and the complex patterns of parallelism in graph analytics applications. Most current parallel abstractions and implementations fail to provide solutions for at least one of them.
Comments
CACM Administrator
An online appendix for this article entitled "Research Directions" may be found under the Source Materials tab in the ACM Digital Library at http://dl.acm.org/citation.cfm?id=2901919, or at http://bit.ly/23HryIA
--CACM Administrator
Displaying 1 comment