Multisearch techniques for implementing data structures on a meshconnected computer . 

M. J. Atallah, F. Dehne, R. Miller, A. RauChaplin, and J.J. Tsay 

Abstract: The {\em multisearch problem} is defined as follows. Given a data structure $D$ modeled as a graph with $n$ constantdegree nodes, perform $O(n)$ searches on $D$. Let $r$ be the length of the longest search path associated with a search process, and assume that the paths are determined ``online''. That is, the search paths may overlap arbitrarily. In this paper, we solve the multisearch problem for certain classes of graphs in $O(\sqrt{n} + {r} \frac{\sqrt{n}}{\log n})$ time on a $\sqrt{n} \times \sqrt{n}$ meshconnected computer. For many data structures, the search path traversed when answering one search query has length $r=O(\log n)$. For these cases, our algorithm processes $O(n)$ such queries in asymptotically optimal $\Theta(\sqrt{n})$ time. The classes of graphs we consider contain many of the important data structures that arise in practice, ranging from simple trees to Kirkpatrick hierarchical search DAGs. Multisearch is a useful abstraction that can be used to implement parallel versions of standard sequential data structures on a mesh. As example applications, we consider a variety of parallel online tree traversals, as well as hierarchical representations of polyhedra and its myriad of applications (linespolyhedron intersection queries, multiple tangent plane determination, intersecting convex polyhedra, and threedimensional convex hull). 

paper.pdf 
paper.ps 

