Parallel Ordered Sets Using Join

Abstract

The ordered set is one of the most important data type in both theoretical algorithm design and analysis and practical programming. In this paper we study the set operations on two ordered sets, including Union, Intersect and Difference, based on four types of balanced Binary Search Trees (BST) including AVL trees, red-black trees, weight balanced trees and treaps. We introduced only one subroutine Join that needs to be implemented differently for each balanced BST, and on top of which we can implement generic, simple and efficient parallel functions for ordered sets. We first prove the work-efficiency of these Join-based set functions using a generic proof working for all the four types of balanced BSTs. We also implemented and tested our algorithm on all the four balancing schemes. Interestingly the implementations on all four data structures and three set functions perform similarly in time and speedup (more than 45x on 64 cores). We also compare the performance of our implementation to other existing libraries and algorithms.

Cited by in corpus (14)

• Parallel Batch-Dynamic Graph Connectivity
• PAM: Parallel Augmented Maps
• Parallel Write-Efficient Algorithms and Data Structures for Computational Geometry
• ConnectIt: A Framework for Static and Incremental Parallel Graph Connectivity Algorithms
• CPMA: An Efficient Batch-Parallel Compressed Set Without Pointers
• Many Sequential Iterative Algorithms Can Be Parallel and (Nearly) Work-efficient
• Multiversion Concurrency with Bounded Delay and Precise Garbage Collection
• Parallel Working-Set Search Structures
• Sage: Parallel Semi-Asymmetric Graph Algorithms for NVRAMs
• Constant-Time Snapshots with Applications to Concurrent Data Structures
• Optimal Multithreaded Batch-Parallel 2-3 Trees
• Efficient Stepping Algorithms and Implementations for Parallel Shortest Paths
• Concurrent Data Structures Made Easy (Extended Version)
• Analysis of Work-Stealing and Parallel Cache Complexity