Datalography: Scaling datalog graph analytics on graph processing systems
| Autor: | Vicky Papavasileiou, Alin Deutsch, Walaa Eldin Moustafa, Kenneth Yocum |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Theoretical computer science
Graph database Distributed database Dataflow Computer science business.industry Graph theory 02 engineering and technology computer.software_genre Graph Datalog Asynchronous communication Analytics 020204 information systems 0202 electrical engineering electronic engineering information engineering Graph (abstract data type) 020201 artificial intelligence & image processing business computer computer.programming_language |
| Zdroj: | IEEE BigData |
| DOI: | 10.1109/bigdata.2016.7840589 |
| Popis: | This paper presents the first Datalog evaluation engine for executing graph analytics over BSP-style graph processing engines. Building on recent advances in Datalog that support efficient evaluation of aggregates functions, it is now easy for data scientists to author many important graph algorithms succinctly. Without the burden of low-level parallelization and optimization, data scientists can avoid programming to the quirks of the latest high-performance distributed computing framework. Where prior approaches build bespoke evaluation engines or modify generalized dataflow processing engines to achieve performance, this work shows how to efficiently evaluate Datalog directly on BSP-style graph processing engines such as Giraph. Datalography incorporates both traditional Datalog optimizations, such as semi-naive evaluation, and new evaluation algorithms and optimization techniques for efficient distributed evaluation of Datalog queries on graph processing engines. In particular we develop evaluation techniques that take advantage of super vertices, eager aggregation, and asynchronous execution to optimize graph processing on Pregel-like systems. We implement our algorithms on top of Apache Giraph and our results indicate that Datalography competes with native, tuned implementations, with some analytics running up to 9 times faster. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|