Optimal Cooperative Search in Fractional Cascaded Data Structures

Fractional cascading is a technique designed to allow efficient sequential search in a graph with catalogs of total size n. The search consists of locating a key in the catalogs along a path. In this paper we show how to preprocess a variety of fractional cascaded data structures whose underlying graph is a tree so that searching can be done efficiently in parallel. The preprocessing takes O(log n) time with n= log n processors on an EREW PRAM. For a balanced binary tree cooperative search along root-to-leaf paths can be done in O((log n)= log p) time using p processors on a CREW PRAM. Both of these time/processor constraints are optimal. The searching in the fractional cascaded data structure can be either explicit, in which the search path is specified before the search starts, or implicit, in which the branching is determined at each node. We apply this technique to a variety of geometric problems, including point location, range search, and segment intersection search. (September 5..