1994
Multisearch Techniques: Parallel Data Structures on MeshConnected Computers
Publication
Publication
Journal of Parallel and Distributed Computing , Volume 20  Issue 1 p. 1 13
The 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([formula] + r ([formula]/log n)) time on a [formula] × [formula]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 Θ([formula]) 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 (linepolyhedron intersection queries, multiple tangent plane determination, intersecting convex polyhedra, and threedimensional convex hull).
Additional Metadata  

dx.doi.org/10.1006/jpdc.1994.1001  
Journal of Parallel and Distributed Computing  
Organisation  School of Computer Science 
Atallah, M.J., Dehne, F, Miller, R., Rauchaplin, A., & Tsay, J.J. (1994). Multisearch Techniques: Parallel Data Structures on MeshConnected Computers. Journal of Parallel and Distributed Computing, 20(1), 1–13. doi:10.1006/jpdc.1994.1001
