Specializing parallel data structures for Datalog. (7th January 2020)

• Record Type: Journal Article
• Authors: Jordan, Herbert; Subotić, Pavle; Zhao, David; Scholz, Bernhard
• Other Names: Tian Hui guestEditor.; Liew Alan Wee‐Chung guestEditor.; Shen Hong guestEditor.; Si Min guestEditor.; Chen Quan guestEditor.; Huang Zhiyi guestEditor.
• Is Part Of: Concurrency and computation. Volume 34:Number 2(2022)
• Page Start: n/a
• Page End: n/a
• Publication Date: 2020-01-07
• Subjects: B‐tree -- Datalog -- parallel data structure -- Trie; Parallel processing (Electronic computers) -- Periodicals; Parallel computers -- Periodicals; 004.35
• DOI: 10.1002/cpe.5643
• Languages: English
• ISSNs: 1532-0626

Abstract

Summary: We see a resurgence of Datalog in a variety of applications, including program analysis, networking, data integration, cloud computing, and security. The large‐scale and complexity of these applications need the efficient management of data in relations. Hence, Datalog implementations require new data structures for managing relations that (1) are parallel, (2) are highly specialized for Datalog evaluation, and (3) can accommodate different workloads depending on the applications concerning memory consumption and computational efficiency. In this article, we present a data structure framework for relations that is specialized for shared‐memory parallel Datalog implementations such as the soufflé Datalog compiler. The data structure framework permits a portfolio of different data structures depending on the workload. We also introduce two concrete parallel data structures for relations, designed for various workloads. Our benchmarks demonstrate a speed‐up of up to 6× by using a portfolio of data structures compared with using a B‐tree alone, showing the advantage of our data structure framework.