OPTIMAL COOPERATIVE SEARCH IN FRACTIONAL CASCADED DATA-STRUCTURES

Fractional cascading is a technique designed to allow efficient sequen tial search in a graph with catalogs of total size n. The search consi sts of locating a key in the catalogs along a path. In this paper we s how how to preprocess a variety of fractional cascaded data structures whose underlying graph is a tree so that searching can be done effici ently in parallel. The preprocessing takes O (log n) time with n/log n processors on an EREW PRAM. For a balanced binary tree, cooperative s earch along root-to-leaf paths can be done in O ((log n)/log p) time u sing p processors on a CREW PRAM. Both of these time/processor constra ints are optimal. The searching in the fractional cascaded data struct ure can be either explicit, in which the search path is specified befo re the search starts, or implicit, in which the branching is determine d at each node. We apply this technique to a variety of geometric prob lems, including point location, range search, and segment intersection search.