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 models 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 running time of an algorithm in the external memory model is defined the number of reads and writes to memory required. 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.

Model

The cache on the left holds ${\frac {M}{B}}$ blocks of size $B$ each, for a total of $M$ objects. The external memory on the right is unbounded.

The model consists of a processor with an internal memory or cache of size $M$, connected to an unbounded external memory. Both the internal and external memory are divided into blocks of size $B$. One input/output operation consists of moving a block of $B$ contiguous elements from external to internal memory, and the running time of an algorithm is determined by the number of these input/output operations.

Algorithms

Algorithms in the external memory model take advantage of the fact that retrieving one object from external memory retrieves an entire block of size $B$. This property is sometimes referred to as locality.

Searching for an element among $N$ objects is possible in the external memory model is possible using a B-tree with branching factor $B$. Using a B-tree, searching, insertion, and deletion can be achieved in $O(\log _{B}N)$ time (in Big O notation). Information theoretically, this is the minimum running time possible for these operations, so using a B-tree is asymptotically optimal.

Using external sorting, such as a ${\frac {M}{B}}$-way merge sort, sorting $N$ elements in the external memory model is possible in $O({\frac {N}{B}}\log _{\frac {M}{B}}{\frac {N}{B}})$ time, which is similarly asymptotically optimal.

The permutation problem is to rearrange $N$ elements into a specific permutation. This can either be done either by sorting, which requires the above sorting runtime, or inserting each element in order and ignoring the benefit of locality. Thus, permutation can be done in $O(\min(N,{\frac {N}{B}}\log _{\frac {M}{B}}{\frac {N}{B}}))$ time.

Applications

The external memory model captures the memory hierarchy, which is not modeled in other common models used in analyzing data structures, such as the random access machine. The model is also useful for analyzing algorithms that work on datasets too big to fit in internal memory.

See also

• Cache-oblivious algorithm