TR-187: Multisearch Techniques for Implementing Data Structures on a Mesh-Connected Computer

Abstract

The multisearch problem consists of efficiently performing 0( n) search processes on a data structure modeled as a graph G with n constant-degree nodes. Denote by r the length of the longest search path associated with a search process, and assume that the paths are determined “on-line”. In this
paper, we solve the multisearch problem in 0( fa+ r 1o1,.) time on a fa x Jn mesh-connected computer. For most data structures, the search path traversed when answering one search query has
length r = 0(log n). For these cases, our algorithm processes 0( n) such queries in asymptotically optimal time, 0( Jn). The classes of graphs considered contain most of the important data structures that arise in practice (ranging from simple trees to Kirkpatrick hierarchical search DAGs).
Multisearch is a useful abstraction that models many specific problems and can be used to im­plement parallel data structures on a mesh. As example applications, we consider interval trees and the related multiple interval intersection search, as well as hierarchical representations of polyhedra and its myriads of applications ( e.g., lines-polyhedron intersection queries, multiple tangent plane determination, intersecting convex polyhedra, and three-dimensional convex hull).