Finalized:Sunday, March 1, 2015
Author(s):Christopher R. Aberger, Andres Nötzli, Kunle Olukotun, Christopher Ré
We present a graph pattern engine, EmptyHeaded, that uses recent algorithmic advances in join processing to compile patterns into Boolean algebra operations that exploit SIMD parallelism. The EmptyHeaded engine demonstrates that treating graph patterns as a general join processing problem can compete with and often outperform both specialized approaches and existing OLAP systems on graph queries. The core Boolean algebra operation performed in EmptyHeaded is set intersection. Extracting SIMD parallelism during set intersections on graph data is challenging because graph data can be skewed in several different ways. Our contributions are a demonstration of this new type of engine with Boolean algebra at its core, an exploration of set intersection representations and algorithms for set intersections that are optimized for skew. We demonstrate that EmptyHeaded outperforms specialized graph engines by over an order of magnitude and relational systems by over two orders of magnitude. Our results suggest that this new style of engine is a promising new direction for future graph engines and accelerators.
Christopher R. Aberger, Andres Nötzli, Kunle Olukotun, Christopher Ré. (2015). EmptyHeaded: Boolean Algebra Based Graph Processing. ArXiv:1503.02368This material is based upon work supported by the National Science Foundation under Grant No. 1343760. Opinions, findings, conclusions or recommendations expressed are those of the authors and do not reflect the views of the NSF.