Fractional Cascading

Fractional Cascading: One Search, Many Catalogs

Suppose a query value $x$ must be located in $k$ sorted catalogs

$$C_1,C_2,\ldots,C_k,$$

each containing at most $n$ keys. A predecessor query asks for the greatest key at most $x$ in every catalog. Running binary search independently is the obvious solution, but it repeats nearly the same navigation $k$ times:

$$O(k\log n).$$

Fractional cascading reorganizes the catalogs so that one binary search supplies enough positional information to continue through every remaining catalog in constant time apiece. For a chain of catalogs, the query becomes

$$O(\log n+k),$$

using linear additional space. The technique does not make binary search itself faster. It makes the result of one search reusable in nearby sorted lists.

Why ordinary pointers are not enough

Imagine storing, beside every item of $C_i$, its insertion position in $C_{i+1}$. If a binary search in $C_i$ ends between keys $a$ and $b$, their pointers may delimit a huge interval in $C_{i+1}$. We would still need another binary search.

Fractional cascading prevents that huge interval. Working from bottom to top, it creates an augmented catalog $A_i$ by merging the real catalog $C_i$ with every other item sampled from $A_{i+1}$:

$$A_k=C_k,\qquad A_i=C_i\;\cup\;\operatorname{sample}(A_{i+1}).$$

Every entry in $A_i$ stores two bridge positions:

• a catalog bridge to the first item in $C_i$ that is not smaller;
• a down bridge to the first item in $A_{i+1}$ that is not smaller.

Because every second item of $A_{i+1}$ was promoted, no two promoted items hide more than one unpromoted item between them. Once a query is bracketed in $A_i$, its down bridge lands at, or within one neighboring position of, the correct bracket in $A_{i+1}$.

A complete three-catalog trace

Use these real catalogs:

The displayed sampling parity is merely a convention; choosing the other parity gives the same asymptotic guarantee. Now query $x=19$.

1. Binary-search $A_1$ once. The first augmented key at least $19$ is $20$, and its predecessor is $16$. The catalog bridge reports $operatorname{pred}_{C_1}(19)=16$.
2. The $20$ entry was promoted from $A_2$, so its down bridge lands exactly on $20$ there. Inspecting that position and its predecessor $14$ identifies the bracket for $19$. The catalog bridge reports $operatorname{pred}_{C_2}(19)=14$.
3. Around that bracket, the next sampled boundary from $A_3$ is $25$. Its down bridge lands on $25$; one step left reaches $18$. Therefore $operatorname{pred}_{C_3}(19)=18$.

Only the first level used logarithmic search. Later levels examined constant-size neighborhoods.

Construction and query pseudocode

The implementation below emphasizes the invariant rather than object layout. merge_with_origin retains whether an entry is real or promoted. lower_bound_links computes, by a linear two-pointer scan, the first not-smaller position in a target array. A production implementation also defines stable behavior for duplicate keys, often by ordering (key, catalog_id, occurrence_id).

from bisect import bisect_left

def build(catalogs):
    """Return augmented levels with catalog and downward bridge arrays."""
    levels = [None] * len(catalogs)
    below = []
    for i in range(len(catalogs) - 1, -1, -1):
        promoted = below[::2]                 # fixed sampling parity
        values = merge_sorted(catalogs[i], promoted)
        to_real = lower_bound_links(values, catalogs[i])
        to_down = lower_bound_links(values, below) if below else None
        levels[i] = (values, to_real, to_down)
        below = values
    return levels

def predecessors(levels, catalogs, x):
    values, _, _ = levels[0]
    pos = bisect_left(values, x)              # the only binary search
    answers = []

    for i, (values, to_real, to_down) in enumerate(levels):
        pos = correct_locally(values, pos, x) # inspect O(1) neighbors
        r = to_real[pos] if pos < len(values) else len(catalogs[i])
        if r < len(catalogs[i]) and catalogs[i][r] == x:
            answers.append(catalogs[i][r])
        else:
            answers.append(catalogs[i][r - 1] if r > 0 else None)
        if i + 1 < len(levels):
            anchor = min(pos, len(values) - 1)
            pos = to_down[anchor]

    return answers

correct_locally is constant time only because the bridge invariant proves that pos is already within a constant number of entries of the next lower bound. Replacing it with an unbounded scan would hide a lost complexity guarantee.

Why the space stays linear

Let $m_i=|C_i|$. Since level $i$ imports only half of $A_{i+1}$,

$$|A_i|\le m_i+\frac{|A_{i+1}|}{2}.$$

Expanding the recurrence shows that an item copied through several levels contributes a geometric series $1+1/2+1/4+\cdots<2$. Consequently,

$$\sum_i |A_i|=O\!\left(\sum_i m_i\right).$$

Bottom-up construction merges already sorted sequences and creates bridge arrays with synchronized scans, so preprocessing is linear in the total augmented size once the original catalogs are sorted. The constants include values or references plus two indices per augmented entry.

The range-tree payoff

In a two-dimensional range tree, a query rectangle $[x_1,x_2]\times[y_1,y_2]$ decomposes the $x$-range into $O(\log n)$ canonical nodes. Each node stores its subtree’s points sorted by $y$. Without linking, two binary searches per catalog cost $O(\log^2 n)$ before reporting.

Fractional cascading links the $y$-catalogs along the relevant search paths. Search for $y_1$ and $y_2$ at the root once, then carry both positions downward in constant time per visited level. The counting or reporting query becomes $O(\log n+k)$, where $k$ is the output size. See Orthogonal Range Searching for the surrounding range-tree construction and canonical-subset argument.

Here $N$ is total catalog size and $r$ is reported output size.

Correctness intuition

At a level boundary, take the two consecutive promoted keys of $A_{i+1}$ that surround $x$. With every-other sampling, at most one lower-level augmented key lies strictly between them. The search position in $A_i$ identifies one of those promoted boundaries. Its down bridge therefore reaches a position adjacent to the true lower bound of $x$ in $A_{i+1}$. A constant comparison resolves the ambiguity. Inductively, the correct bracket propagates through all levels; catalog bridges translate each augmented bracket into the answer for the real catalog.

Sentinels $-\infty$ and $+\infty$ can simplify edge cases. Without them, implementations must explicitly represent “no predecessor” and the insertion position after the final key. Duplicates require a declared answer—first occurrence, last occurrence, or key only—and bridge construction must use the matching lower- or upper-bound convention everywhere.

Static strength, dynamic friction

Classical fractional cascading is strongest when catalogs are related and rarely updated. Inserting one key changes sampling parity and bridge destinations; a naive repair can propagate through many augmented levels. Deletions create the same problem, and stale bridges silently invalidate the constant-neighborhood lemma.

Dynamic fractional-cascading structures exist, but they use more intricate blocking, balanced structures, and indirection, with weaker constants and update bounds. In application code, practical choices are often simpler:

• batch updates and rebuild when the changed fraction crosses a threshold;
• use immutable snapshots with background reconstruction;
• keep a small unsorted or separately sorted delta and search it in addition to the static structure;
• retain independent binary searches when $k$ is small or updates dominate queries.

The broader lesson is reusable beyond this data structure: when repeated searches travel through related ordered sets, preserve where the previous search ended. Fractional cascading turns that intuition into a provable invariant by spending a linear number of carefully sampled copies and bridges.