Fractional Cascading - Example

Example

As a simple example of fractional cascading, consider the following problem. We are given as input a collection of k ordered lists L_i of real numbers, such that the total length Σ|L_i| of all lists is n, and must process them so that we can perform binary searches for a query value q in each of the k lists. For instance, with k = 4 and n = 17,

L₁ = 2.4, 6.4, 6.5, 8.0, 9.3

L₂ = 2.3, 2.5, 2.6

L₃ = 1.3, 4.4, 6.2, 6.6

L₄ = 1.1, 3.5, 4.6, 7.9, 8.1

The simplest solution to this searching problem is just to store each list separately. If we do so, the space requirement is O(n), but the time to perform a query is O(k log(n/k)), as we must perform a separate binary search in each of k lists. The worst case for querying this structure occurs when each of the k lists has equal size n/k, so each of the k binary searches involved in a query takes time O(log(n/k)).

A second solution allows faster queries at the expense of more space: we may merge all the k lists into a single big list L, and associate with each item x of L a list of the results of searching for x in each of the smaller lists L_i. If we describe an element of this merged list as x where x is the numerical value and a, b, c, and d are the positions (the first number has position 0) of the next element at least as large as x 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

L = 1.1, 1.3, 2.3, 2.4, 2.5, 2.6,

3.5, 4.4, 4.6, 6.2, 6.4, 6.5,

6.6, 7.9, 8.0, 8.1, 9.3

This merged solution allows a query in time O(log n + k): simply search for q in L and then report the results stored at the item x found by this search. For instance, if q = 5.0, searching for q in L finds the item 6.2, from which we return the results L₁ = 6.4, L₂ (a flag value indicating that q is past the end of L₂), L₃ = 6.2, and L₄ = 7.9. However, this solution pays a high penalty in space complexity: it uses space O(kn) as each of the n items in L must store a list of k search results.

Fractional cascading allows this same searching problem to be solved with time and space bounds meeting the best of both worlds: query time O(log n + k), and space O(n). The fractional cascading solution is to store a new sequence of lists M_i. The final list in this sequence, M_k, is equal to L_k; each earlier list M_i is formed by merging L_i with every second item from M_{i + 1}. With each item x in this merged list, we store two numbers: the position resulting from searching for x in L_i and the position resulting from searching for x in M_{i + 1}. For the data above, this would give us the following lists:

M₁ = 2.4, 2.5, 3.5, 6.4, 6.5, 7.9, 8, 9.3

M₂ = 2.3, 2.5, 2.6, 3.5, 6.2, 7.9

M₃ = 1.3, 3.5, 4.4, 6.2, 6.6, 7.9

M₄ = 1.1, 3.5, 4.6, 7.9, 8.1

Suppose we wish to perform a query in this structure, for q = 5. We first do a standard binary search for q in M₁, finding the value 6.4. The "1" in 6.4, tells us that the search for q in L₁ should return L₁ = 6.4. The "5" in 6.4 tells us that the approximate location of q in M₂ is position 5. More precisely, binary searching for q in M₂ would return either the value 7.9 at position 5, or the value 6.2 one place earlier. By comparing q to 6.2, and observing that it is smaller, we determine that the correct search result in M₂ is 6.2. The first "3" in 6.2 tells us that the search for q in L₂ should return L₂, a flag value meaning that q is past the end of list L₂. The second "3" in 6.2 tells us that the approximate location of q in M₃ is position 3. More precisely, binary searching for q in M₃ would return either the value 6.2 at position 3, or the value 4.4 one place earlier. A comparison of q with the smaller value 4.4 shows us that the correct search result in M₃ is 6.2. The "2" in 6.2 tells us that the search for q in L₃ should return L₃ = 6.2, and the "3" in 6.2 tells us that the result of searching for q in M₄ is either M₄ = 7.9 or M₄ = 4.6; comparing q with 4.6 shows that the correct result is 7.9 and that the result of searching for q in L₄ is L₄ = 7.9. Thus, we have found q in each of our four lists, by doing a binary search in the single list M₁ followed by a single comparison in each of the successive lists.

More generally, for any data structure of this type, we perform a query by doing a binary search for q in M₁, and determining from the resulting value the position of q in L₁. Then, for each i > 1, we use the known position of q in M_i to find its position in M_{i + 1}. The value associated with the position of q in M_i points to a position in M_{i + 1} that is either the correct result of the binary search for q in M_{i + 1} or is a single step away from that correct result, so stepping from i to i + 1 requires only a single comparison. Thus, the total time for a query is O(log n + k).

In our example, the fractionally cascaded lists have a total of 25 elements, less than twice that of the original input. In general, the size of M_i in this data structure is at most

as may easily be proven by induction. Therefore, the total size of the data structure is at most

as may be seen by regrouping the contributions to the total size coming from the same input list L_i together with each other.