External Memory Data Structures

Lars Arge

In many massive dataset applications the data must be stored in space and query efficient data structures on external storage devices. Often the data needs to be changed dynamically. In this chapter we discuss recent advances in the development of provably worst-case efficient external memory dynamic data structures. We also briefly discuss some of the most popular external data structures used in practice.

Keywords: I/O model, B-trees, Interval trees, Planar point location, Kinetic data structures, Proximity queries.