External memory model

In theoretical computer science, the external memory model (also called the I/O model or disk access model) is a model of computation that captures the behavior of computers that use magnetic storage. It captures the fact that read and write operations are much faster in a cache than in main memory, and that reads long contiguous blocks is faster than reading randomly using a disk read-and-write head. The model was introduced by Alok Aggarwal and David Vitter in 1988. The external memory model is related to the cache-oblivious model, but algorithms in the external memory model may know the block size.

See also

• Cache-oblivious algorithm