Fundamental Limits of External Memory Priority Queues

18 concepts5 papers4 proposals

When datasets grow too large to fit into a computer's fast internal memory (RAM), they must be stored in external memory, such as an SSD or hard drive. In this setting, the standard metric for algorithmic efficiency changes completely. Instead of counting individual CPU instructions, we measure performance by the number of Input/Output (I/O) operations required to transfer blocks of data between external and internal memory.

In standard internal memory, data structures like priority queues can seamlessly support operations like Insert, ExtractMin, and DecreaseKey in logarithmic or even constant time. However, when data is partitioned into rigid blocks of size $B$, a fundamental tension emerges between the sequential nature of block transfers and the random-access nature of dynamic updates.

The Baseline: Equivalence to Sorting

To understand why external memory data structures behave differently, we must look at how basic priority queues handle block transfers. In external memory, we cannot afford to read or write a block for every single element we manipulate. Instead, we must batch operations so that every I/O transfer processes a full block of $B$ elements.

This batching principle creates a deep theoretical connection between priority queues and sorting. In Equivalence between Priority Queues and Sorting in External Memory, Zhewei Wei et al. demonstrated that priority queues and sorting are computationally equivalent in the external memory model. By treating a sorting algorithm as a "black box," the authors designed a priority queue where the amortized I/O cost per operation exactly matches the per-key cost of sorting.

This equivalence works because basic operations like Insert and ExtractMin can be buffered in internal memory. When the buffer fills up, its contents are sorted and merged with larger, sorted runs on disk—directly mirroring the mechanics of external merge sort. This establishes a highly efficient baseline for large-scale data processing. As shown by André Hernich et al. in Randomized Computations on Large Data Sets: Tight Lower Bounds, even basic verification tasks (like checking if a list is sorted) require a logarithmic number of sequential passes over the data, defining a strict theoretical floor for external memory algorithms.

The Bottleneck of Blind Updates

The sorting-equivalence model breaks down when a data structure must support the DecreaseKey operation, which updates the priority of an element already residing inside the queue. This operation is vital for graph algorithms like Dijkstra's Single Source Shortest Paths (SSSP).

The core difficulty, as articulated by Shunhua Jiang et al. in A Faster External Memory Priority Queue with DecreaseKeys, is that a DecreaseKey operation requires locating and updating an element without prior knowledge of its current value or its exact block location on disk.

Internal Memory (RAM)          External Memory (Disk Blocks)
+------------------------+     +---------+ +---------+ +---------+
| Buffer:                |     | Block 1 | | Block 2 | | Block 3 |
| DecreaseKey(Element X) | --> | ???     | | ElementX| | ???     |
+------------------------+     +---------+ +---------+ +---------+
                                    ^           ^           ^
                                    |___________|___________|
                                     Where is Element X? 
                                     Searching costs an I/O!

If an algorithm attempts to track the exact location of every key by maintaining an index, updating that index itself introduces an expensive I/O penalty. If it does not maintain an index, it must search blindly through disk blocks.

This bottleneck is not a flaw of existing implementations, but an inescapable mathematical reality. In DecreaseKeys are expensive for external memory priority queues, Kasper Eenberg et al. proved a lower bound of $\Omega((N/B) \lg \lg NB)$ I/Os for priority queues that support DecreaseKey. This proof confirms that the inclusion of DecreaseKey forces an inherent performance degradation compared to simpler queues, placing a fundamental limit on how fast dense graph algorithms can run in external memory.

Bridging the Gap Lazily

To overcome this bottleneck and match the theoretical lower bounds, algorithms must avoid immediate disk lookups. Instead of finding and modifying an element the moment its priority decreases, optimal structures handle updates lazily.

In A Faster External Memory Priority Queue with DecreaseKeys, the authors closed the long-standing gap between practice and theory by achieving an expected amortized I/O complexity of $O(\frac{\log B}{\log \log N})$ per operation. The intuition behind this optimization relies on routing updates through a hierarchy of buffers.

When a DecreaseKey command is issued, the data structure simply logs the modification in an internal memory buffer. As buffers fill up, these update logs are pushed down into larger, structured levels on disk. The actual reconciliation happens at the last possible second: when an ExtractMin operation pulls an element to the top, the structure cross-references it with the pending updates encountered along the way. By transforming random disk lookups into structured, batched streams of update logs, the algorithm avoids blind searching and achieves optimal I/O efficiency.

A Parallel in Static Queries

This fundamental constraint of block-structured memory is not unique to dynamic priority queues; it also governs static data structures. Even when a dataset never changes, the physical arrangement of data into blocks restricts how efficiently we can query it.

Consider the static Range Minima Query (RMQ) problem, where we must find the minimum value within an arbitrary index range of a fixed array. One might expect that a static dataset would allow for a perfectly linear I/O complexity during preprocessing and querying. However, Peyman Afshani demonstrated in I/O-Efficient Range Minima Queries that achieving linear I/O complexity for static RMQ is impossible.

Just as a DecreaseKey operation is constrained by the difficulty of locating an element across blocks, an RMQ query is constrained by the alignment of query boundaries with block boundaries. To answer a range query without scanning the entire range, an algorithm must store precomputed summaries. Because these summaries span across multiple blocks, certain queries inevitably force non-linear I/O jumps. By proving matching upper and lower bounds, the author showed that block-based storage introduces non-linear mathematical floors to even the most straightforward retrieval tasks.

Key Foundational Work

Randomized Computations on Large Data Sets: Tight Lower Bounds (2007) — contributed 1 concept elements to this direction.
Equivalence between Priority Queues and Sorting in External Memory (2012) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_external_memory_priority_queue_complexit_a91b48c6,
  title = {external memory priority queue complexity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/external-memory-priority-queue-complexity/rdr_a91b48c6cd7f4d1b99034afef6a73aa0},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_external_memory_priority_queue_complexit_a91b48c6_v1,
  title = {external memory priority queue complexity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/external-memory-priority-queue-complexity/rdr_a91b48c6cd7f4d1b99034afef6a73aa0/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake