Recursive Star-Tree Parallel Data Structure
Omer Berkman, Uzi Vishkin · SIAM Journal on Computing · 1993
This paper introduces a novel parallel data structure called the recursive star-tree (denoted “${}^ * $-tree”). For its definition a generalization of the $ * $ functional is used (where for a function $f * f(n) = \min \{ {i|f^{(i)} (n) \leqslant 1} \}$ and $f^{(i)} $ is the ith iterate of f). Recursive ${}^ * $-trees are derived by using recursion in the spirit of the inverse Ackermann function. The recursive ${}^ * $-tree data structure leads to a new design paradigm for parallel algorithms. This paradigm allows for extremely fast parallel computations, specifically, $O(\alpha (n))$ time (where $\alpha (n)$ is the inverse of the Ackermann function), using an optimal number of processors on the (weakest) concurrent-read, concurrent-write parallel random-access machine (CRCW PRAM). These computations need only constant time, and use an optimal number of processors if the following nonstandard assumption about the model of parallel computation is added to the CRCW PRAM: an extremely small number of processors each can write simultaneously into different bits of the same word. Applications include finding lowest common ancestors in trees by a new algorithm that is considerably simpler than the known algorithms for the problem, restricted domain merging, parentheses matching, and a new parallel reducibility.
Cited by 186 works. doi:10.1137/0222017
Authors
References
- Efficiency of a Good But Not Linear Set Union Algorithm
- Parallel Prefix Computation
- Fast Algorithms for Finding Nearest Common Ancestors
- Parallelism in Comparison Problems
- On Finding Lowest Common Ancestors: Simplification and Parallelization
- An Efficient Parallel Biconnectivity Algorithm
- Fast parallel and serial approximate string matching
- Routing, merging, and sorting on parallel models of computation
- Finding the maximum, merging, and sorting in a parallel computation model
- Deterministic coin tossing with applications to optimal parallel list ranking