Fractional cascading revisited

Sen , S. D. (1995) Fractional cascading revisited Journal of Algorithms, 19 (2). pp. 161-172. ISSN 0196-6774

Full text not available from this repository.

Official URL:

Related URL:


We present an alternative implementation of the fractional cascading data structure of Chazelle and Guibas (Algorithmica1 (1986), 133-162) that performs iterative search for a key in multiple ordered lists. The construction of our data structure uses randomization and simplifies the algorithm of Chazelle and Guibas, vastly making it practical to implement. Although our bounds are asymptotically similar to the earlier ones, there are improvements in the constant factors. Our analysis is novel and captures some of the inherent difficulties associated with the fractional cascading data structure. In particular, we use tools from branching process theory and derive some useful asymptotic bounds. The probability of deviation from the expected performance bounds decreases exponentially with number of keys. Also, under a restricted model, we obtain efficient bounds for updates in the data structure.

Item Type:Article
Source:Copyright of this article belongs to Elsevier Science.
ID Code:53429
Deposited On:08 Aug 2011 12:08
Last Modified:08 Aug 2011 12:08

Repository Staff Only: item control page