Optimal Cooperative Search in Fractional Cascaded Data Structures

R. Tamassia and J. S. Vitter. ``Optimal Cooperative Search in Fractional Cascaded Data Structures,'' invited paper in special issue on on parallel computing in Algorithmica 15(2), February 1996, 154-171. A shortened version appears in Proceedings of the 2nd Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA '90), Crete, Greece, July 1990, 307-316.

Full text (gzip-compressed postscript)

Full text (Adobe pdf format)

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.