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

**
**

**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).

Russ Miller (miller@cse.buffalo.edu)