Fully dynamic search trees for an extension of the BSP model
Fully dynamic search trees for an extension of the BSP model
复制标题
用于 BSP 模型扩展的完全动态搜索树
DOI：
10.1145/237502.237562
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
Wolfgang Dittrich
中科院分区：
文献类型：
--
作者：
A. Bäumker;Wolfgang Dittrich
BSP模型扩展的全动态搜索树* Armin Baumker和Wolfgang Dittrich {abk， Dittrich}(~uni-paderborn.de帕德伯恩大学数学与计算机系和Heinz Nixdorf研究所D-33095帕德伯恩，德国科学我们提出了在插入和删除下保持2-3树的并行算法。该算法是为Valiant的BSP模型（BSP*）的扩展而设计的，并减少了通信中涉及的开销。BSP*-模型由Baumker等人在2010年提出。我们对数据结构的分析超越了标准的渐近分析：我们使用Valiant的c-最优y的概念。直观地说，c-最优算法倾向于随着输入大小的增加（p表示处理器的数量）而加速p/c，其中通信时间渐近小于计算时间。我们的第一种方法允许l-最优搜索和平平化c-最优插入和删除小常数c。第二种方法允许2-最优搜索，c-最优删除和插入小常数c。对于BSP*参数的大范围，这两种结果都有1 - 0(1)的概率，其中范围随着输入大小的增加而变大，第一种方法允许更大的范围。此外，这两种方法都是内存效率高的，它们使用的内存总量与存储集的大小m成正比。我们的结果通过支持完全动态的搜索树而不是静态的搜索树改进了以前的结果，并且显著减少了通信时间。此外，我们的算法使用分组通信。
Fully Dynamic Search Trees for an Extension of the BSP Model* Armin Baumker and Wolfgang Dittrich {abk, dittrich}(~uni-paderborn.de Department of Mathematics and Computer and Heinz Nixdorf Institute University of Paderborn D-33095 Paderborn, Germany Science 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 communicant ion. 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-optimalit y. 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 l-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.