Fully Dynamic Search Trees for an Extension of the BSP Model

Abstract

We present parallel algorithms that maintain a 2-3 tree under insertions and deletions. The algorithms are designed for an extension of Valiant's BSP model, BSP*, that and reduction of the overhead involved in communication. The BSP*-model is introduced by Baumker et al. in [2]. Our analysis of the data structure goes beyond standard asymptotic analysis: We use Valiant's notion of c-optimality. Intuitively c-optimal algorithms tend to speedup p/c with growing input size (p denotes the number of processors), where the communication time is asymptotically smaller than the computation time.
Our first approach allows 1-optimal searching and amortized c-optimal insertion and deletion for a small constant c. The second one allows 2-optimal searching, and c-optimal deletion and insertion for a small constant c. Both results hold with probability 1 - o(1) for wide ranges of BSP*- parameters, where the ranges become larger with growing input sizes. The first approach allows much larger ranges. Further, both approaches are memory efficient, their total amount of memory used is proportional to the size m of the set being stored.
Our results improve previous results by supporting a fully dynamic search tree rather than a static one, and by significantly reducing the communication time. Further our algorithms use blockwise communication.