THE FOLD / CO-OP / THE HANDOFF / THE FRACTIONAL CASCADING
THE FRACTIONAL CASCADING
search many sorted lists with one search plus bridges
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Fractional cascading answers the same query against many sorted lists with a single binary search instead of one per list. It weaves a fraction of each list into the previous one and adds bridge pointers, so once you locate the query in the first list, every other list’s answer is a constant-time hop away — turning k searches of O(log n) each into O(log n + k) total.
It is the classic speedup for iterated search in computational geometry.
LIT verified live: over 300 random setups of k sorted lists, the successor fractional cascading reports in each list equals an independent binary search in that list (window.__fractionalcascading). FIG no framing; exact.
It is the classic speedup for iterated search in computational geometry.
LIT verified live: over 300 random setups of k sorted lists, the successor fractional cascading reports in each list equals an independent binary search in that list (window.__fractionalcascading). FIG no framing; exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-handoff — the found position is handed from one list to the next along a bridge, no fresh search needed. Fractional cascading is that chain of handoffs. AVAN (AI) built the instrument: the augmented lists with promoted elements, the bridge pointers, the single-search-then-hop query, the per-list cross-check.
Credit as content: Bernard Chazelle & Leonidas Guibas (1986). The weave: David names the handoff; I weave the lists together so one search cascades through them all, and confirm each answer matches an independent search.
Credit as content: Bernard Chazelle & Leonidas Guibas (1986). The weave: David names the handoff; I weave the lists together so one search cascades through them all, and confirm each answer matches an independent search.
3 ONE DIMENSION
Every other element of one list is promoted into the previous list, carrying a bridge back. A position found here points to a position there — the query slides across for free.
4 TWO DIMENSIONS · INTERACTIVE
Several sorted lists; a query’s successor in each is found by one search plus bridge hops, checked against per-list binary search.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the single search, then bridges carrying it through every list.
AVAN’s addition (the inverse-companion): you do one binary search and then hop. By weaving a fraction of each list into the previous one, the position found in list i gives the position in list i+1 in O(1), so k searches collapse to one search plus k constant hops. The inverse of ‘search each list independently’ is ‘search once and let each list hand its answer to the next.’ Magenta is the k−1 redundant binary searches; green is the single search and its O(1) bridges. Shared structure between the lists carries the query along.
LIT Genuine fractional cascading (Chazelle & Guibas 1986). Verified live: the augmented-list structure with bridge pointers returns, via one binary search plus O(1) hops, the same per-list successor as an independent binary search in each list, across 300 random setups of k sorted lists (window.__fractionalcascading.matchesNaive).
FIG No framing: the augmented lists with promoted elements, the bridge pointers, the single-search-then-hop query, and the per-list cross-check run in-browser and agree exactly. The AVAN inverse is honest — a position found in list i gives the position in list i+1 in O(1), so k independent searches collapse to one search plus k hops; magenta is the k-1 redundant searches, green the single search + bridges. Shared structure carries the query along.
FIG No framing: the augmented lists with promoted elements, the bridge pointers, the single-search-then-hop query, and the per-list cross-check run in-browser and agree exactly. The AVAN inverse is honest — a position found in list i gives the position in list i+1 in O(1), so k independent searches collapse to one search plus k hops; magenta is the k-1 redundant searches, green the single search + bridges. Shared structure carries the query along.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE HANDOFF · David Lee Wise (ROOT0), with AVAN