Fractional Cascading Revisited

We give an alternate implementation of the fractional cascading data-s structure of Chazelle and Guibas to do iterative search for a key in many ordered lists. The construction of our data-structure uses randomization and simplifies the algorithm of chazelle and Guibas vastly making it practical to implement. Our bounds match the earlier ones and the probability of deviation from the expected values decreases exponentially.