semiexternal

Semiexternal memory is a theoretical model used to analyze algorithms that operate on data sets too large to fit entirely in a computer’s main memory. In this model, the data reside on external storage such as disks, while a limited amount of fast internal memory holds a working set of items and intermediate results during computation. The primary performance measure is the number of I/O operations between internal and external memory.

In a semiexternal algorithm, the working set in internal memory remains small relative to the full data, so processing proceeds by streaming and buffering. The algorithm loads blocks from external memory into internal memory, performs computations, and writes outputs back, often in multi-pass or pipelined fashion. The model emphasizes minimizing I/O over pure CPU time.

Semiexternal approaches sit between internal-memory algorithms (which assume all data fits in RAM) and fully external memory models (where data remains on disk for most of the computation). They are used to study problems such as sorting and graph processing when data cannot fit in memory, providing a framework to analyze trade-offs between memory size and I/O cost.

Applications include semi-external sorting, semi-external graph algorithms, and database operations that require buffering and streaming large datasets. The semiexternal framework helps derive lower bounds and guide algorithm design for data-intensive tasks.

See also: external memory model; external sorting; I/O complexity; RAM model.