External storage model

The external storage model is a model from theoretical computer science that describes the complexity of algorithms in relation to the use of several storage hierarchies. The model was first described in 1987 by Alok Aggarwal and Jeffrey S. Vitter. In contrast to the classic RAM model, which describes the runtime of an algorithm based on the number of operations on the processor and access to any large, fast main memory, the external memory model uses an abstract machine model consisting of two memory levels. This is a fast main memory which the size M possesses, and an external memory, which has a sufficiently large for the solution of the problem size, this parameter is not a model, and a block size B . The length of the entry is denoted by N , which is stored in N / B blocks on the external memory. In realistic scenarios this is N >> M. To load an element or B elements within a block into the main memory, access to the external memory is required. This access is also known as I / O.

The aim of the model is to minimize the number of accesses to the external memory (I / Os) that are necessary to solve a given problem.

Reading consecutively saved data

One of the basic primitives used in external storage is reading X consecutive data. In order to read this data, I / Os must be carried out. If the entire input is read, this is referred to as a scan (N) , which has the I / O compatibility of I / Os. ${\displaystyle {\mathcal {O}}(X/B)}$ ${\displaystyle {\mathcal {O}}(N/B)}$

Sort in external memory

In the external memory, N data can be sorted with I / Os using a modified mergesort algorithm . ${\displaystyle {\mathcal {O}}(N/B\cdot \log _{M/B}(N/B))}$

Individual evidence

1. ^ The I / O complexity of sorting and related problems . In: Algorithms And Complexity - Automata, Languages ​​and Programming, Volume 267 of the series Lecture Notes in Computer Science pp. 467–478, doi : 10.1007 / 3-540-18088-5_40