Multisearch techniques for implementing data structures on a mesh-connected computer .

M. J. Atallah, F. Dehne, R. Miller, A. Rau-Chaplin, and J.-J. Tsay

Abstract: The {\em multisearch problem} is defined as follows. Given a data structure $D$ modeled as a graph with $n$ constant-degree 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 ``on-line''. 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}$ mesh-connected 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 (lines-polyhedron intersection queries, multiple tangent plane determination, intersecting convex polyhedra, and three-dimensional convex hull).