Startseite > Publikationen > Publikationen


Bäumker, Armin;Meyer auf der Heide, Friedhelm:

Communication Efficient Parallel Searching.

IRREGULAR 1997 : S. 233-254, Jun. 1997


Abstract. Searching is one of the most important algorithmic problems, used as a subroutine in many applications. Accordingly, designing search algorithms is in the center of research on data structures since decades. In this paper we aim to survey recent developments in designing parallel search algorithms where parallel machines are used to answer many search queries in parallel, so called multisearch algorithms. We briefly describe the current state of multisearcb algorithms based on hashing and binary search, as they are developed for abstract parallel models like the PRAM. The main part of the paper describes deterministic and randomized multisearch algorithms that are very communication efficient. As a computation and cost model we employ Valiant's BSP model and its variant BSP* due to Bäumker et al.




author = {B{\"a}umker, Armin and Meyer auf der Heide, Friedhelm},
title = {Communication Efficient Parallel Searching},
journal = {IRREGULAR 1997},
pages = {233-254},
month = jun,
year = {1997},

BibTeX in die Zwischenablage kopieren