A priority queue repeatedly hands back its smallest item. Many graph algorithms also need a fourth operation, DecreaseKey, which lowers the priority of an item already in the queue. Dijkstra's shortest-path algorithm is the standard example. When the queue is too large for fast memory, the cost that matters is how many fixed-size blocks move between a small fast memory and a large slow one. For queues with DecreaseKey, that cost is now understood on a two-level machine. Eenberg et al. proved that DecreaseKey makes such queues strictly more expensive than sorting (DecreaseKeys are expensive for external memory priority queues). Jiang and Larsen then built a queue that matches this lower bound (A Faster External Memory Priority Queue with DecreaseKeys). Their design, however, is sized by hand for one block size $B$ and one memory size $M$. Real machines have five or six levels (L1, L2, L3, RAM, SSD), and a structure tuned for one level can thrash at the others. The authors list the cache-oblivious version as open. A cache-oblivious structure is one written with no knowledge of $B$ or $M$ that is still efficient at every level at once.
We propose to build that structure and test it. The idea is to keep Jiang and Larsen's lazy, buffered tournament tree but lay it out recursively, in the style of funnels and van Emde Boas trees. Each recursive piece gets a signal buffer and an approximate-membership filter whose sizes are fixed functions of that piece's own size, never of $B$. A filter here means a compact bit array that answers "is this item probably below this node?" For any block size there is then some recursion scale at which a piece, its buffer and its filter fit in a constant number of blocks. The cache-aware cost analysis can be replayed at that scale. The claim is that this gives the optimal DecreaseKey cost at every level of the hierarchy simultaneously. We also make an honest empirical check of the regime where this matters: directed shortest paths whose "already settled" bookkeeping overflows the cache levels in question.
Core Claim
We claim there is a priority queue supporting Insert, Delete, ExtractMin and DecreaseKey, with no $B$ or $M$ in its code, that meets two conditions. First, under the ideal-cache model with a tall-cache assumption ($M \ge B^2$), it achieves expected amortized block-transfer cost within a constant factor of the cache-aware optimum at every level. Second, on real hardware it beats both a cache-aware queue tuned for a single level and the usual workaround of re-inserting items and discarding stale copies. The workaround wins only when the bookkeeping array fits in the level being measured.
The research file's summaries quote the cache-aware bound in inconsistent normalizations. Per operation it appears as $O(\log B/\log\log N)$; the sequence lower bound appears as $\Omega((N/B)\lg\lg NB)$. A per-operation cost that must sit below the lower bound for sorting-free queues needs the $1/B$ factor. Our first deliverable is therefore to fix the exact statement from the two papers. Our working target, consistent with the sequence lower bound, is
$$ T_{\text{op}}(N,B) = O\!\left(\frac{1}{B}\,\frac{\log B}{\log\log N}\right)\quad\text{expected amortized block transfers per operation, for every level's } B, $$
where $N$ is the number of items. Whatever the correct form turns out to be, success means matching the cache-aware Jiang–Larsen cost at each level up to a constant.
The lower-bound side needs no new work. A cache-oblivious algorithm is in particular a cache-aware algorithm at each level, so the Eenberg et al. bound applies at each level for free. The open content is entirely the upper bound.
Why this is the right gap
The obvious connection between the two directions is already done for queues without DecreaseKey. The 2004 Dagstuhl collection (04301 Abstracts Collection) describes the buffer heap and bucket heap, which reach sorting cost cache-obliviously. Wei et al. show cache-aware queues without DecreaseKey are equivalent to sorting (Equivalence between Priority Queues and Sorting in External Memory). Plugging Funnel Sort into Wei et al.'s reduction is a natural project, but it inherits the exclusion of DecreaseKey and would at most reproduce what buffer heaps already give.
The DecreaseKey case differs in kind. Lower bounds alone are not the difficulty. The cache-aware solution uses two devices whose sizes are tied to $B$: per-node buffers that are flushed when full, and per-node filters that keep a DecreaseKey from searching subtrees that do not contain the item. Neither device appears in any cache-oblivious queue in the file.
Notably, Jiang and Larsen's branching factor $t=\log^{0.01}N$ depends on $N$, not on $B$. This is what makes the problem look tractable: the tree shape is already oblivious, and only buffer capacities and filter dimensions need re-deriving.
Research Program
The construction takes the $t$-ary tournament tree, of height $O(\log N/\log t)$, and stores it in a recursive layout. The tree is cut at half its height into a top tree and many bottom trees, each stored contiguously and recursively, as in the van Emde Boas layout analyzed by Locality-of-Reference Optimality of Cache-Oblivious Algorithms.
At each recursion boundary, a piece holding up to $k$ items receives three things. It gets a signal buffer of capacity polynomial in $k$, for pending inserts, deletes and decreases, sized in the spirit of the funnel buffers behind Funnel Sort. It also gets a "todo" buffer for pulled items, as in Jiang and Larsen. Finally, it gets a membership filter over the identities stored below it, using $O(k)$ bits.
The analysis follows the funnelsort template. Fix any $B$ and let $\ell$ be the recursion level at which pieces have size roughly $B^c$ for a small constant $c$. Pieces at level $\ell$ and their buffers then fit in $O(1)$ blocks under the tall-cache assumption. Every flush across a level-$\ell$ boundary moves $\Omega(B)$ signals per block touched, so the per-level accounting of the cache-aware proof applies with that $B$.
The real technical obstacle is filter accuracy. In the cache-aware design the false-positive rate is chosen against $B$, so wasted descents cost less than the useful work. Obliviously, we will give filters at depth $d$ of the recursion a false-positive rate that shrinks geometrically in $d$. Wasted work then sums to a constant factor at every scale, at the cost of extra filter bits per item. Whether those extra bits keep total space linear is the second analytical question.
The file motivates caution on space. Cache-oblivious range reporting with optimal queries requires superlinear space shows that obliviousness forces $\Omega(N(\log\log N)^\epsilon)$ space for some range-reporting problems. We will therefore either prove $O(N)$ words, or isolate where a $\log\log$ factor enters and test whether it is needed.
Integer identities in $\{1,\dots,N\}$ are assumed, as in Jiang and Larsen; arbitrary comparison keys are out of scope. Bounds stay amortized, and the latency spikes from flushes are measured but not eliminated.
We will implement the structure in C++ over a single array (no pointers), alongside the competitors below. Each structure will be measured in two ways. The first is an ideal-cache simulator that counts block transfers simultaneously for a grid of $(M,B)$ pairs, from $(32\text{KB}, 64\text{B})$ up to $(4\text{GB}, 64\text{KB})$. The second is real hardware, with hardware counters for L1, L2, L3 and TLB misses and an SSD-backed memory map for the disk level. Address translation gets attention because Cache-Oblivious VAT-Algorithms showed regular recursive algorithms such as Funnel Sort pay at most a 4 × tree-depth factor over the ideal-cache cost, but it did not analyze filter probes or lazy buffers. We report TLB misses separately to see whether the recursive layout keeps that overhead bounded.
Baselines
The naive reference point is a binary heap with a position array, so DecreaseKey is an in-place sift-up. The operating system pages it to the SSD. This is what most implementations do, and it shows how bad the problem is without any external-memory design. It runs on the same machine, the same workloads, and the same memory limit set through cgroups.
The strongest existing method on this exact question is the cache-aware Jiang–Larsen queue (A Faster External Memory Priority Queue with DecreaseKeys), implemented from the paper. Its strongest reported result is theoretical: Dijkstra in $O(|V| + |E|\frac{\log B}{\log\log|V|})$ I/Os as quoted in the file. There is no reported result on Lacuna for measured block transfers or wall-clock time of any DecreaseKey external priority queue. Our implementation will therefore be the first empirical reference, and we will publish it.
To be fair to the cache-aware queue, we give it a tuning budget: a grid search over buffer and filter sizes, run separately for each memory level, with the best configuration chosen per level on held-out graphs. We then report two numbers. The first is its best-tuned cost at the level it was tuned for. The second is its cost at every other level, using that same single configuration, because that is how it would actually ship.
Beating it means two things. Our structure must stay within 1.5× of the tuned cache-aware queue at that queue's own target level. It must also beat that single configuration's total cost, summed over levels and weighted by measured miss latency.
The second strong competitor is the existing cache-oblivious approach without DecreaseKey. This is a buffer heap or bucket heap of the kind surveyed in 04301 Abstracts Collection, used with re-insertion of improved entries and a settled-vertex array to discard stale copies. We implement it with the same array-based engineering and the same compiler flags. Beating it means fewer total block transfers on directed graphs once the settled array exceeds the measured level. Conceding to it below that threshold is an expected outcome, not a failure.
Two ablations isolate the key ingredient. The first removes the filters entirely, so every DecreaseKey is pushed down as a blind signal and resolved lazily. The second keeps filters but gives them one fixed size and false-positive rate chosen for a single $B$. If the geometric filter schedule is what makes the design oblivious, the second ablation should match us at its tuned $B$ and lose elsewhere. The first should lose everywhere on DecreaseKey-heavy workloads.
Why not just…?
Why not just re-insert improved entries into an existing cache-oblivious queue and throw away stale copies? This is the most serious threat, and we treat it as such. The file's own argument against it compares $\frac{\log B}{\log\log|V|}$ against $\frac{1}{B}\log_{M/B}\frac{|E|}{B}$. That comparison is not sound as written, because the two expressions are in different normalizations. With the $1/B$ restored and a tall cache, sorting-cost queues are actually cheaper per operation than any DecreaseKey queue can be, which is exactly the separation Eenberg et al. proved.
The real cost of re-insertion is elsewhere. Deciding whether an extracted entry is stale needs a lookup in a per-vertex settled array, one random access per extracted entry. For directed graphs that is up to $|E|$ uncached accesses whenever the array exceeds the level in question.
On a two-level machine with ample RAM, a road-network settled array fits in memory and re-insertion will likely win at the RAM–SSD level. At L2 and L3 it will not fit. That is precisely where a cache-oblivious DecreaseKey queue should help. The experiment that settles this sweeps graph size so the settled array crosses each cache level in turn, and reports the crossover point per level.
Why not just query the hardware for $B$ and $M$ and run the cache-aware queue? One configuration targets one level. Prior cache-oblivious systems work reports that tuning for one level causes stalls at others. EaseDB's cache-oblivious operators reduced L1, L2 and TLB stalls together on an Intel P4, and packed-memory-array storage gave "over 2x" faster table scans (Cache-Oblivious Query Processing). Cache-oblivious B-trees were reported as "sometimes by a factor of two" faster than tuned disk-model B-trees (04301 Abstracts Collection). These results concern different structures, so they motivate rather than prove our case. The per-level detuning measurement in the Baselines section is the direct test. A per-level-tuned queue that matches us everywhere would refute the practical half of the claim.
Why not just coarsen or predict priorities? Multiresolution queues bucket priorities and removed a heap operation costing 6.5% of CPU in the Bro network monitor's timer handling (Multiresolution Priority Queues). They do this by giving up exact ordering, which exact Dijkstra cannot accept. Learning-augmented queues cut Dijkstra comparisons on the London road network by nearly 75% (Learning-Augmented Priority Queues). They count comparisons in internal memory, however, and do no block batching, so they say nothing about transfers. Prediction is complementary: a predicted rank could seed where an insert enters our tree. That is left as an extension rather than a competitor.
Proposed Experiments
Workloads come from the benchmarks in the file. The first is Dijkstra on the London, Brussels, Paris and New York road networks used by Learning-Augmented Priority Queues. We use them both undirected and as directed versions with randomized one-way edges, and scale them synthetically by tiling, from cache-resident to roughly 10× RAM. The second is denser synthetic directed graphs, where $|E|/|V|$ ranges from 4 to 256, to stress DecreaseKey frequency. The third is a timer-management trace in the style of the Bro evaluation, where nearly every operation is a DecreaseKey or Delete.
Metrics are simulated block transfers per operation at each $(M,B)$ pair, measured misses at each hardware level and TLB, wall-clock time, peak space in words, and the 99.9th-percentile operation latency, to expose flush spikes.
The decisive checks are three. First, in simulation, our structure's transfers per operation must track the cache-aware optimum within a constant factor across the whole $(M,B)$ grid. The no-filter ablation must not. A curve that drifts away from the optimum as $B$ grows would mean the geometric filter schedule fails and the analysis is wrong.
Second, on directed graphs, the crossover against re-insertion must occur where the settled array exceeds each level, as predicted. If re-insertion wins even when the array is far larger than the level, the practical motivation for DecreaseKey collapses and we will report that.
Third, space must stay within a small constant of $N$ words as $N$ grows. A measured $\log\log N$-like growth would point toward a superlinear-space phenomenon like the one in range reporting, and would redirect the theoretical work toward proving it.
References
- DecreaseKeys are expensive for external memory priority queues
- A Faster External Memory Priority Queue with DecreaseKeys
- 04301 Abstracts Collection - Cache-Oblivious and Cache-Aware Algorithms
- Equivalence between Priority Queues and Sorting in External Memory
- Locality-of-Reference Optimality of Cache-Oblivious Algorithms
- Cache-oblivious range reporting with optimal queries requires superlinear space
- Cache-Oblivious VAT-Algorithms
- Cache-Oblivious Query Processing
- Multiresolution Priority Queues
- Learning-Augmented Priority Queues