Fractional Cascading at Block Granularity: Searching Many Levels per Cache Miss

Many geometric data structures answer a query by walking down a tree and doing a sorted-list search at every node on the way. Range trees, segment trees and the multi-level structures behind spatial queries all work this way. Fractional cascading is the classical trick that makes the walk cheap: after one binary search at the top, each further level costs only a constant number of steps, because every list carries "bridge" pointers into its child's list. On a real machine, a constant number of steps can still mean one cache miss per level, since every node's list sits somewhere else in memory. Laying the tree out cleverly cannot change that. The bridges are pointers, and following $k$ of them into $k$ different arrays costs about $k$ memory transfers whatever the layout. We propose to replace bridges with a packed, word-parallel encoding in which about $\log B$ consecutive levels of the walk are resolved by reading a single memory block of $B$ words. A walk of length $k$ would then cost about $k/\log B$ transfers instead of $k$.

The proposal has three parts. The first is a cache-aware structure, meaning one tuned to a known block size, that reaches this bound with essentially linear extra space. The second is a cache-oblivious version, meaning one that works well for every block size at once without knowing any of them. The third asks, conjecturally, whether this obliviousness forces superlinear space, in the same way known lower bounds force it for cache-oblivious range reporting. Lower bounds will be argued in the cell probe model, which counts only memory reads and treats arithmetic as free. A block-transfer lower bound is simply a cell probe bound with $B$-word cells, so it holds whatever computation is done. The upper bound uses only shifts and popcounts, and we will measure its real CPU cost, which the cell probe model hides.

Core Claim

Restrict attention to nested catalogs. These are trees in which each node's sorted list is split among its children's lists, as in a 2D range tree, where the list at a node holds the $y$-coordinates of the points in its $x$-slab. Classical fractional cascading over such a tree is linear space. Its cost is $O(\log_B N + k)$ block transfers for a walk of length $k$, where $N$ is the total list size, and it still costs that when laid out in a recursive, van Emde Boas-style order. Our claim is that the per-level term can be divided by roughly $\log B$:

$$ Q(k) = O\!\left(\log_B N + \frac{k}{\log B}\right), $$

Here $Q(k)$ is the number of block transfers. The cache-aware version uses $O(N)$ words plus $O(N)$ extra bits. For the cache-oblivious version we conjecture that the same query bound is achievable with only an $O(\log\log N)$ factor of extra space, and that some superlinear factor is unavoidable.

The mechanism is easiest to see one level at a time. In a nested catalog, your position in a child's list equals the number of elements before your position in the parent's list that went to that child. Storing one bit per parent element ("went left/right") plus sampled prefix counts turns each bridge into a rank computation. Now group $h$ consecutive levels. Each element of the group's top list stores an $h$-bit "path symbol" recording which of the $2^h$ descendants it lands in. Every $s$ positions, the structure stores prefix counts for all $2^h-1$ internal nodes of the group. A query position needs one counter lookup plus a scan of at most $s$ packed symbols, and that yields its rank at every level of the group at once.

If $s\cdot h$ bits fit in one block of $B$ words of $w$ bits, the scan costs one transfer. The counters cost about $(N/s)\,2^h w \approx N\,2^h h/B$ bits per group. Choosing $h \approx \log B - \log\log B$ keeps that at $O(N)$ bits per group while each transfer resolves $\Theta(\log B)$ levels. The scan is about $B$ word operations of popcount. In the cell probe model those operations are free. On hardware they are where the cost sits, and whether they are cheap relative to a cache miss is an empirical question we will answer.

For the cache-oblivious version, the grouping is built at every scale $h = 1, 2, 4, \dots$ simultaneously, and the levels are laid out recursively so that whatever the true block size, some scale matches it. Paying linear bits at each of $\Theta(\log\log N)$ scales is the source of the conjectured $\log\log$ space factor. This is exactly the shape of the separation Cache-oblivious range reporting with optimal queries requires superlinear space proved for range reporting, where obliviousness to $B$ forced $\Omega(N(\log\log N)^\epsilon)$ space.

Relation to Prior Work

The method's starting point is classical cascading from Visibility and Intersection Problems in Plane Geometry, which samples part of each child list into the parent and adds bridge pointers so that each level costs $O(1)$ comparisons. We keep that per-level guarantee but drop the pointers, because pointers are what tie the cost to one transfer per level. Dynamic Fractional Cascading shows how to support updates at an extra $\log\log N$ per level. We treat only the static case and say so; dynamization is left aside.

Two results constrain what is possible. A Lower Bound for Dynamic Fractional Cascading proves an $\Omega(\log n\sqrt{\log\log n})$ query bound for dynamic cascading, but only on a pointer machine, which cannot do address arithmetic. Our static structure does not contradict it: it relies on exactly the bit-level arithmetic a pointer machine forbids. That reinforces the paper's own point that its model does not settle the RAM or cell probe question. Cache-oblivious range reporting with optimal queries requires superlinear space and Improved Space Bounds for Cache-Oblivious Range Reporting prove superlinear-space lower bounds of $\Omega(N(\log\log N)^\epsilon)$ and $\Omega(N\log^\epsilon N)$ for cache-oblivious reporting with optimal queries. They do not study iterative search along a path. We aim to adapt their argument, which forces duplication across block scales, to cascaded search, where the "output" is a vector of ranks rather than reported points.

The log-shaving results Hopcroft's Problem, Log-Star Shaving, 2D Fractional Cascading, and Decision Trees and Simplex Range Searching Revisited show that word-level packing and table lookups can remove logarithmic factors in multi-level structures. They count operations, not memory transfers, and their deterministic variants rely on huge precomputed tables. Our packing is deliberately modest (popcount over one block), so that it is implementable.

For the hardware model, Locality-of-Reference Optimality of Cache-Oblivious Algorithms shows that ideal-cache optimality carries over to continuous locality costs for $B$-stable problems. Cache-Oblivious VAT-Algorithms shows that address translation adds hidden costs unless the cache is tall. Neither analyzes structures that hop between many independent arrays. Our design cuts the number of distinct arrays touched per query by a factor of $\log B$, so we expect it to help the translation cache too, and we will measure that.

Research Program

The theoretical work has three pieces. The first is to prove the cache-aware bound, including the space accounting above and an initial-search phase that uses a standard B-tree or van Emde Boas tree on the root list. The second is to build the multi-scale cache-oblivious structure and bound both its I/O cost and its space; the target is $O(\log\log N)$ extra words per element or better.

The third is a lower bound in the cell probe model with $B$-word cells. A first, easy step formalizes why pointer-style cascading pays $\Omega(k)$: each level's answer lives in a separate region. The real question is whether any linear-space structure can beat $k/\log B$. Our intuition is a counting argument: resolving $h$ levels in one probe needs per-block information about $2^h$ subtrees. The harder and more interesting goal is the oblivious separation, that is, showing that $O(\log_B N + k/\log B)$ for all $B$ simultaneously needs superlinear space, by adapting the multi-scale duplication argument of the range-reporting lower bounds. We will report honestly if that adaptation fails. A clean $O(\log\log N)$ upper bound without a lower bound is still a result.

The engineering work is a C++ implementation of 2D orthogonal range counting over a range tree whose $y$-searches use, in turn, independent searches, classical bridges in recursive layout, one-bit rank vectors, and our $h$-level groups (cache-aware with $h$ tuned, and cache-oblivious multi-scale). All variants share the same top-level tree and the same code for the initial search.

Baselines

The naive reference point is independent searching. Each node on the walk holds its sorted list in van Emde Boas order and is searched from scratch, for $O(k\log_B N)$ transfers. This is what Circle-Segment Intersection Queries in Connected Geometric Graphs effectively does when it evaluates an oracle independently at each tree level, and that paper names fractional cascading as the open route to cutting its $O(k\log^3 n)$ query cost. Beating it is necessary but not impressive.

The strongest pointer-based competitor is classical fractional cascading with bridges, stored with every list contiguous and nodes in recursive van Emde Boas order. It is the textbook method and already wins the operation count. Beating it means measurably fewer misses per level at equal or lower space, specifically a misses-per-level ratio that falls as $h$ grows, roughly like $1/h$.

The ablation that isolates our ingredient is the $h=1$ version: one bit per element and prefix counts per level. This is the familiar rank-bitvector replacement for bridges, which we take from general practice; no reported result found on Lacuna for it in this setting. It is also the reviewer's most natural alternative. If $h>1$ does not beat it, multi-level grouping buys nothing.

For end-to-end context we compare against a Morton-order packed array in the style of Packed-Memory Quadtree, which reports range query "speedups of up to 7x" over B-trees and R-trees and "answers 90% of top-k queries in under 4 ms" on its 210-million-record Twitter stream. That figure is for a different task mix, so we will rerun the method ourselves on our counting queries rather than compare against the number.

All methods get the same data, the same queries, a single core, the same compiler flags, and the same tuning budget. The cache-aware variants may tune $h$ and $s$ on a held-out query set. The oblivious variant gets no tuning. No reported result found on Lacuna for cascaded range counting on any of these datasets.

Why not just…?

Why not just lay out classical bridges in van Emde Boas order? The layout cannot help, because the $k$ lists on a query's walk are $k$ distinct arrays. The query lands at a position that depends on the query in each of them, so for large lists each hop touches a new block. The bridge-baseline measurements will show whether misses per level stay near one, as this argument predicts.

Why not just use a cache-aware B-tree-style structure tuned to the hardware block size? This is a real threat to the cache-oblivious half of the proposal, though not to the cache-aware half, which is itself such a structure. Cache-Oblivious Query Processing reports that tuning for one cache level thrashes others and that calibrated parameters are often wrong. We will test this directly by tuning $h$ for L1, L2 and the last-level cache in turn, and recording misses at every level. If one tuned setting is within a few percent of the oblivious variant everywhere, we will say the oblivious structure is of theoretical interest only.

Why not just flatten the points onto a space-filling curve? The Packed-Memory Quadtree shows this is fast in practice for streaming data, but a curve offers no worst-case guarantee for rectangle queries, which split into many curve intervals. We include it as a baseline and report worst-case as well as median latency, where we expect the difference to show.

Why not just use one-bit rank vectors? They remove the pointers but still cost one transfer per level. The $h$-sweep is designed to settle whether grouping levels matters.

Proposed Experiments

The data are segment endpoints from the Germany road network (about 1.1 million edges) and the Taiwan road network (about 5 million edges) used by the circle-segment intersection paper, the 22.3-million-node OpenStreetMap Germany graph, and, if obtainable, the Twitter geolocated stream. Queries are random and adversarially thin rectangles. Metrics are hardware-counted misses at L1, L2, last-level cache and the translation cache, per level of the walk; wall-clock latency (median and 99th percentile); space in bits per point; and, in a simulated ideal cache, transfers per query as a function of $B$ from 8 to 4096 words.

The first decisive check is the slope of transfers against $k$. The bridge and one-bit variants should sit near one transfer per level, the grouped variants near $1/h$. A flat slope for the grouped variant would falsify the core claim.

The second check is obliviousness. Across the simulated $B$ sweep, the multi-scale variant should stay within a constant factor of the variant tuned to each $B$, and its space should grow by no more than a $\log\log N$ factor as $N$ grows from $10^5$ to the largest dataset.

The third check is the cell-probe blind spot. We will report CPU cycles spent in popcount scans next to miss counts, and flag any regime where the scans cost more than the misses they save. That would mean the probe-count advantage does not survive on real hardware.