I/O-Space Trade-Offs

Lars Arge
Jakob Pagter

April 2000

Abstract:

We define external memory (or I/O) models which capture space complexity and develop a general technique for deriving I/O-space trade-offs in these models from internal memory model time-space trade-offs. Using this technique we show strong I/O-space product lower bounds for Sorting and Element Distinctness. We also develop new space efficient external memory Sorting algorithms

Last modified: 2003-06-08 by webmaster.