External Memory Model
Jump to navigation
Jump to search
See: Random Access Machine, Register Machine.
References
2009
- (Schweikardt, 2009) Nicole Schweikardt. (2009). “Machine Models for Query Processing.” In: SIGMOD Record, 38(2).
- The basic external memory model (cf., e.g., [27]) can be viewed as a refinement of the RAM model where memory is divided into internal memory, capable of storing up to M data items, and external memory of unbounded size. Data present in internal memory can be accessed quickly (as in the RAM model). Data present in external memory can only be accessed by an operation called Input/Output communication (I/O, for short) that moves a contiguous block of B data items between internal and external memory. Initially, the N input items are stored in external memory. One typically assumes that M < N and 1 6 B 6 M/2.
1996
- (Kumar & Schwabe, 1996) ⇒ Vijay Kumar, and Eric J. Schwabe. (1996). “Improved Algorithms and Data Structures for Solving Graph Problems in External Memory.” In: IEEE Symposium on Parallel and Distributed Processing, (SPDP 1996). [doi:10.1109/SPDP.1996.570330].