Distributed Triangle Counting in the Graphulo Matrix Math Library
arXiv:1709.01054 · doi:10.1109/HPEC.2017.8091041
Abstract
Triangle counting is a key algorithm for large graph analysis. The Graphulo library provides a framework for implementing graph algorithms on the Apache Accumulo distributed database. In this work we adapt two algorithms for counting triangles, one that uses the adjacency matrix and another that also uses the incidence matrix, to the Graphulo library for server-side processing inside Accumulo. Cloud-based experiments show a similar performance profile for these different approaches on the family of power law Graph500 graphs, for which data skew increasingly bottlenecks. These results motivate the design of skew-aware hybrid algorithms that we propose for future work.
Honorable mention in the 2017 IEEE HPEC's Graph Challenge
References in corpus (9)
- Exploiting Multiple Levels of Parallelism in Sparse Matrix-Matrix Multiplication
- The BigDAWG Polystore System and Architecture
- Static Graph Challenge: Subgraph Isomorphism
- LaraDB: A Minimalist Kernel for Linear and Relational Algebra Computation
- Graphulo: Linear Algebra Graph Kernels for NoSQL Databases
- Graphulo Implementation of Server-Side Sparse Matrix Multiply in the Accumulo Database
- Using a Power Law Distribution to describe Big Data
- From NoSQL Accumulo to NewSQL Graphulo: Design and Utility of Graph Algorithms inside a BigTable Database
- Benchmarking the Graphulo Processing Framework