arXiv (Cornell University) · 2016 · 11 citations · 21 references
ComputingComputer EngineeringComputer ScienceAlgorithmsParallel AlgorithmsParallel ComputingAlgorithm AnalysisData ParallelismData Structure AlgorithmsParallel Algorithm DesignParallel Data StructuresSet OperationsAvl TreesBalanced Binary Search TreesBinary Search TreesOrdered Set OperationsParallel Avl TreesParallel Binary Search TreesParallel Red-black TreesRed-black Trees
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.
21
Self-adjusting binary search trees
Daniel D. Sleator, Robert E. Tarjan · Journal of the ACM · 1985 · 1.2K citations · Full text
The Parallel Evaluation of General Arithmetic Expressions
Richard P. Brent · Journal of the ACM · 1974 · 818 citations · Full text
Symmetric binary B-Trees: Data structure and maintenance algorithms
Rudolf Bayer · Acta Informatica · 1972 · 496 citations
Raimund Seidel, C. Aragon · Algorithmica · 1996 · 281 citations