W. Dittrich, D. Hutchinson, and A. Maheshwari, Blocking in Parallel Multisearch Problems, Proc. Symposium on Parallel Algorithms and Architectures (SPAA'98), Puerto Vallarta, Mexico, June 1998, pp. 98-107.
 

External memory (EM) algorithms are designed for computational problems in which the size of the internal memory of the computer is only a small fraction of the problem size. Block-wise access to data is a central theme in the design of efficient EM algorithms. A similar requirement arises in the transmission of data between processors in certain parallel computation models such as BSP* and CGM, for which block-wise communication is a crucial issue. We consider multisearch problems, where a large number of queries are to be simultaneously processed and satisfied by navigating through large data structures on parallel computers. The examples used originate as BSP* algorithms and we adapt them to the EM situation where the queries and data structure are considered to be much larger than the size of the available internal memory. This paper presents techniques to achieve blocking for I/O as well as for communication in multisearch on the BSP* and EM-BSP* models. In the area of EM algorithms new algorithms for multisearch in balanced trees are described. For search trees up to size $O(n\log n)$ where $n$ is the number of queries, we obtain work-optimal, parallel, EM multisearch algorithms whose I/O and communication time are the same, asymptotically, as the computation time. These algorithms are obtained via the simulation technique of \cite{DDH97}. For larger trees we describe a parallel, EM algorithm which is simultaneously $c$-optimal and I/O-optimal. We give a lower bound to the number of I/O operations required for filtering $n$ queries through a binary or multiway search tree of size $m$ when $m\geq n^{2+\epsilon}$, constant $\epsilon>0$. In the domain of parallel, non-EM algorithms we describe a new $1$-optimal algorithm for BSP* multisearch in optimal trees which communicates in a block-wise fashion.