Cache-Oblivious Algorithms and Data Structures Erik D. Demaine MIT Laboratory for Computer Science, 200 Technology Square, Cambridge, MA 02139, USA, edemaine@mit.edu Abstract. A recent direction in the design of cache-efficient and disk- efficient algorithms and data structures is the notion of cache oblivi- ousness, introduced by Frigo, Leiserson, Prokop, and Ramachandran in 1999. Cache-oblivious