Abstract
The 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} x 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).