On a Sublinear Time Parallel Construction of Optimal Binary Search Trees

TitleOn a Sublinear Time Parallel Construction of Optimal Binary Search Trees
Publication TypeTechnical Report
Year of Publication1993
AuthorsKarpinski, M., & Rytter W.
Other Numbers867

We design an efficient sublinear time parallel construction of optimal binary search trees. The efficiency of the parallel algorithm corresponds to its total work (the product time X processors). Our algorithm works in O(n_1-e) log(n)) time with the total work O(n_2+2e), for an aritrarily small constant 0< e less than or equal to one half. This is optimal within factor n_2e with respect to the best known sequential algorithm given by Knuth, which needs only O(n_2) time due to a monotonicity property of optimal binary search trees, see [6]). It is unknown how to explore this property in an efficient NC construction of binary search trees. Here we show that it can be effectively used in sublinear time parallel computation. Our improvement also relies on the use (in independently processed small subcomputations) of the parallelism present in the Knuth's algorithm. The best known sublinear time algorithms for the construction of binary search trees (as an instance of a more general problem) have O(n_3) work for time larger than n_3/4, see [3] and [7]. For time square root of (n) these algorithms need n_4 work, while our algorithm needs for this time only n_3 work, thus improving the known algorithms by a linear factor. Also if time is O(n_1-e) and e is very small our improvement is close to O(n). Such improvement is similar to the one implied by the monotonicity property in sequential computations (from n_3 sequential time for a more general dynamic programming problem to n_2 time for the special case of optimal binary search trees).

Bibliographic Notes

ICSI Technical Report TR-93-079

Abbreviated Authors

M. Karpinski and W. Rytter

ICSI Publication Type

Technical Report