TR-158: Parallel Fractional Cascading on a Hypercube Multiprocessor

Abstract

In this paper we present a parallel implementation of fractional cascading for hypercube multiprocessors. We show that, if the underlying catalog graph is monotone (as defined in the paper), N multiple look-up queries (including catalog look-ups) can be executed independently, in parallel, in time O(ts log N) on a hypercube multiprocessor of size N, where ts is the sequential time complexity for one multiple look-up query. We apply our method to various problems for which we obtain new efficient hypercube algorithms.