Affordable Access

From NoSQL Accumulo to NewSQL Graphulo: Design and Utility of Graph Algorithms inside a BigTable Database

Authors
  • Hutchison, Dylan
  • Kepner, Jeremy
  • Gadepally, Vijay
  • Howe, Bill
Type
Preprint
Publication Date
Jun 22, 2016
Submission Date
Jun 22, 2016
Identifiers
arXiv ID: 1606.07085
Source
arXiv
License
Yellow
External links

Abstract

Google BigTable's scale-out design for distributed key-value storage inspired a generation of NoSQL databases. Recently the NewSQL paradigm emerged in response to analytic workloads that demand distributed computation local to data storage. Many such analytics take the form of graph algorithms, a trend that motivated the GraphBLAS initiative to standardize a set of matrix math kernels for building graph algorithms. In this article we show how it is possible to implement the GraphBLAS kernels in a BigTable database by presenting the design of Graphulo, a library for executing graph algorithms inside the Apache Accumulo database. We detail the Graphulo implementation of two graph algorithms and conduct experiments comparing their performance to two main-memory matrix math systems. Our results shed insight into the conditions that determine when executing a graph algorithm is faster inside a database versus an external system---in short, that memory requirements and relative I/O are critical factors.

Report this publication

Statistics

Seen <100 times