In computer science, fractional cascading is a technique to speed up a sequence of binary searches for the same value in a sequence of related data structures. The first binary search in the sequence takes a logarithmic amount of time, as is standard for binary searches, but successive searches in the sequence are faster. The original version of fractional cascading, introduced in two papers by Chazelle and Guibas in 1986 (Chazelle & Guibas 1986a; Chazelle & Guibas 1986b), combined the idea of cascading, originating in range searching data structures of Lueker (1978) and Willard (1978), with the idea of fractional sampling, which originated in Chazelle (1983). Later authors introduced more complex forms of fractional cascading that allow the data structure to be maintained as the data changes by a sequence of discrete insertion and deletion events.
Read more about Fractional Cascading: Example, The General Problem, Dynamic Fractional Cascading, Applications
Famous quotes containing the words fractional and/or cascading:
“Hummingbird
stay for a fractional sharp
sweetness, and’s gone, can’t take
more than that.”
—Denise Levertov (b. 1923)
“Have We not made the earth as a cradle and the mountains as pegs? And We created you in pairs, and We appointed your sleep for a rest; and We appointed night for a garment, and We appointed day for a livelihood. And We have built above you seven strong ones, and We appointed a blazing lamp and have sent down out of the rain-clouds water cascading that We may bring forth thereby grain and plants, and gardens luxuriant.”
—Qur’An. “The Tiding,” 78:6-16, trans. by Arthur J. Arberry (1955)