An optimal parallel algorithm for merging using multiselection (Q1322118)

This paper presents an optimal parallel algorithm for the construction of \((a,b)\)-trees -- a generalization of 2-3 trees, 2-3--4 trees, and \(B\)- trees. The authors show the existence of a canonical form for \((a,b)\)- trees, with a very regular structure, which allows them to obtain a scalable parallel algorithm for the construction of a minimum-height \((a,b)\)-tree with \(N\) keys in \(O(N/p + \log \log N)\) time using \(p \leq N/ \log \log N\) processors on the EREW-PRAM model, and \(O(N/p)\) time using \(p \leq N\) processors on the CREW-model. It is shown that the average memory utilization for the canonical form is at least 50\% better than that for the worst-case and is also better than that for a random \((a,b)\)-tree. A significant feature of the proposed parallel algorithm is that its time-complexity depends neither on \(a\) nor on \(b\), and hence this general algorithm is superior to earlier algorithms for parallel construction of \(B\)-trees.