Geoffrey Sanders | 17-ERD-024
Overview
Until now, the most performant massive-scale distributed graph analytic engines have been essentially unusable for anything but the analytic they were tuned to solve. This project built on HavoqGT, a Laboratory-developed, asynchronous, high-performance computing (HPC) graph framework, to advance the tool’s capability as a flexible graph framework, aiming to extend algorithmic capabilities, improve underlying data structures, and develop novel communication paradigms to enable new data-analysis missions. Highlights of the technology we developed include 1) a new distributed communication paradigm dubbed "You've Got Mail" (YGM), 2) a performant exact and fuzzy HPC graph pattern matching approach, and 3) a distributed biased random walk simulation capability.
Impact on Mission
Our project leveraged and advanced Lawrence Livermore National Laboratory's core competencies in HPC, simulation, and data science and augmented data analysis capabilities. Our results have been applied to Laboratory programmatic projects and have attracted interest from new external and internal sponsors.
Publications, Presentations, Etc.
Bromberger, S., et al. 2018. "Improving Estimation of Betweenness Centrality for Scale-Free Graphs." LLNL-TR-741432.
Iwabuchi, K., et al. 2018. "Computing Exact Vertex Eccentricity On Massive-Scale Distributed Graphs." IEEE International Conference on Cluster Computing, CLUSTER 2018, Belfast, UK, September 2018. LLNL-CONF-751522.
Pearce, R. 2017. "Triangle Counting for Scale-Free Graphs at Scale in Distributed Memory." IEEE High Performance Extreme Computing Conference, HPEC 2017, Waltham, MA, September 2017. LLNL-CONF-737552.
Pearce, R. and G. Sanders. 2018. "K-Truss Decomposition for Scale-Free Graphs at Scale in Distributed Memory." IEEE High Performance Extreme Computing Conference, HPEC, September 2018. LLNL-CONF-757957.
Pearce, R., et al. 2019. "One Quadrillion Triangles Queried on One Million Processors." IEEE High Performance Extreme Computing Conference, HPEC, September 2019. LLNL-CONF-789648.
Priest, B., et al. 2018. "Estimating Edge-Local Triangle Count Heavy Hitters in Edge-Linear Time and Almost-Vertex-Linear Space." IEEE High Performance Extreme Computing Conference, HPEC 2018, Waltham, MA, September 2018. LLNL-CONF-757958.
Reza, T., et al. 2017. "Towards Practical and Robust Labeled Pattern Matching in Trillion-Edge Graphs." IEEE International Conference on Cluster Computing, CLUSTER 2017, Honolulu, HI, September 2017. LLNL-CONF-735657.
––– . 2018. "Prunejuice: Pruning Trillion-Edge Graphs to a Precise Pattern-Matching Solution." International Conference for High Performance Computing, Networking, Storage, and Analysis, SC 2018, Dallas, TX, November 2018. LLNL-CONF-748768.
Sanders, G., et al. 2018. "On Large-Scale Graph Generation with Validation of Diverse Triangle Statistics at Edges and Vertices." Graph Algorithms Building Blocks, Vancouver, British Columbia, Canada, May 2018. LLNL-CONF-748352.
