We develop an optimal cache‐oblivious priority queue data structure, supporting insertion, deletion, and delete‐min operations in $O(\frac{1}{B}\log_{M/B}\frac{N}{B})$ amortized memory transfers, where M and B are the memory and block transfer sizes of any two consecutive levels of a multilevel memory hierarchy. In a cache‐oblivious data structure, M and B are not used in the description of the structure. Our structure is as efficient as several previously developed external memory (cache‐aware) priority queue data structures, which all rely crucially on knowledge about M and B. Priority queues are a critical component in many of the best known external memory graph algorithms, and using our cache‐oblivious priority queue we develop several cache‐oblivious graph algorithms.

We develop cache-oblivious data structures for orthogonal range searching, the problem of finding all T points in a set of N points in IRd lying in a query hyper-rectangle. Cache-oblivious data structures are designed to be efficient in arbitrary memory hierarchies.We describe a dynamic linear-size data structure that answers d-dimensional queries in O((N/B)1-1/d+T/B) memory transfers, where B is the block size of any two levels of a multilevel memory hierarchy. A point can be inserted into or deleted from this data structure in O(log2B N) memory transfers. We also develop a static structure for the two-dimensional case that answers queries in O(logB N+T/B) memory transfers using O(N log22 N) space. The analysis of the latter structure requires that B=22c for some non-negative integer constant c.

(MATH) In this paper we develop an optimal cache-oblivious priority queue data structure, supporting insertion, deletion, and deletemin operations in O(1 \over B logM/BN \over B) amortized memory transfers, where M and B are the memory and block transfer sizes of any two consecutive levels of a multilevel memory hierarchy. In a cache-oblivious data structure, M and B are not used in the description of the structure. The bounds match the bounds of several previously developed external-memory (cache-aware) priority queue data structures, which all rely crucially on knowledge about M and B. Priority queues are a critical component in many of the best known external- memory graph algorithms, and using our cache-oblivious priority queue we develop several cache- oblivious graph algorithms.