Paper Info
Title
PaC-Trees: Supporting Parallel and Compressed Purely-Functional Collections
Abstract
Many modern programming languages are shifting toward a functional style for collection interfaces such as sets, maps, and sequences. Functional interfaces offer many advantages, including being safe for parallelism and providing simple and lightweight snapshots. However, existing high-performance functional interfaces such as PAM, which are based on balanced purely-functional trees, incur large space overheads for large-scale data analysis due to storing every element in a separate node in a tree. This paper presents PaC-trees, a purely-functional data structure supporting functional interfaces for sets, maps, and sequences that provides a significant reduction in space over existing approaches. A PaC-tree is a balanced binary search tree which blocks the leaves and compresses the blocks using arrays. We provide novel techniques for compressing and uncompressing the blocks which yield practical parallel functional algorithms for a broad set of operations on PaC-trees such as union, intersection, filter, reduction, and range queries which are both theoretically and practically efficient. Using PaC-trees we designed CPAM, a C++ library that implements the full functionality of PAM, while offering significant extra functionality for compression. CPAM consistently matches or outperforms PAM on a set of microbenchmarks on sets, maps, and sequences while using about a quarter of the space. On applications including inverted indices, 2D range queries, and 1D interval queries, CPAM is competitive with or faster than PAM, while using 2.1-7.8x less space. For static and streaming graph processing, CPAM offers 1.6x faster batch updates while using 1.3-2.6x less space than the state-of-the-art graph processing system Aspen.
Year
DOI
Venue
2022
10.1145/3519939.3523733
PROCEEDINGS OF THE 43RD ACM SIGPLAN INTERNATIONAL CONFERENCE ON PROGRAMMING LANGUAGE DESIGN AND IMPLEMENTATION (PLDI '22)
Keywords
DocType
Citations 
purely-functional data structures, parallel data structures, space-efficient data structures
Conference
0
PageRank 
References 
Authors
0.34
0
4
Name
Order
Citations
PageRank
Laxman Dhulipala101.35
Guy E. Blelloch22927207.30
Yan Gu35710.46
Yihan Sun47311.19