Handbook of Data Structures and Applications, 2nd Edition

35

Cache-Oblivious Data Structures*

Lars Arge

University of Aarhus

Gerth Stølting Brodal

University of Aarhus

Rolf Fagerberg

University of Southern Denmark

35.1The Cache-Oblivious Model

35.2Fundamental Primitives

Van Emde Boas Layout•k-Merger

35.3Dynamic B-Trees

Density Based•Exponential Tree Based

35.4Priority Queues

Merge Based Priority Queue: Funnel Heap•Exponential Level Based Priority Queue

35.52d Orthogonal Range Searching

Cache-Oblivious kd-Tree•Cache-Oblivious Range Tree

Acknowledgments

References

35.1The Cache-Oblivious Model

The memory system of most modern computers consists of a hierarchy of memory levels, with each level acting as a cache for the next; for a typical desktop computer the hierarchy consists of registers, level 1 cache, ...