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 (; ), combined the idea of cascading, originating in range searching data structures of and , with the idea of fractional sampling, which originated in . 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.
Example
As a simple example of fractional cascading, consider the following problem. We are given as input a collection of ordered lists of numbers, such that the total length of all lists is , and must process them so that we can perform binary searches for a query value in each of the lists. For instance, with and , = 24, 64, 65, 80, 93 = 23, 25, 26 = 13, 44, 62, 66 = 11, 35, 46, 79, 81 The simplest solution to this searching problem is just to store each list separately. If we do so, the space requirement is , but the time to perform a query is , as we must perform a separate binary search in each of lists. The worst case for querying this structure occurs when each of the lists has equal size , so each of the binary searches involved in a query takes time .
A second solution allows faster queries at the expense of more space: we may merge all the lists into a single big list , and associate with each item of a list of the results of searching for in each of the smaller lists . If we describe an element of this merged list as where is the numerical value and , , , and are the positions (the first number has position 0) of the next element at least as large as in each of the original input lists (or the position after the end of the list if no such element exists), then we would have = 11[0,0,0,0], 13[0,0,0,1], 23[0,0,1,1], 24[0,1,1,1], 25[1,1,1,1], 26[1,2,1,1], 35[1,3,1,1], 44[1,3,1,2], 46[1,3,2,2], 62[1,3,2,3], 64[1,3,3,3], 65[2,3,3,3], 66[3,3,3,3], 79[3,3,4,3], 80[3,3,4,4], 81[4,3,4,4], 93[4,3,4,5] This merged solution allows a query in time : simply search for in and then report the results stored at the item found by this search. For instance, if , searching for in finds the item 62[1,3,2,3], from which we return the results , (a flag value indicating that is past the end of ), , and . However, this solution pays a high penalty in space complexity: it uses space as each of the items in must store a list of search results.
