Efficient algorithms and data structures for massive data sets

Abstract

For many algorithmic problems traditional algorithms that optimise on the number of instructions executed prove expensive on I Os Novel and very di erent design techniques when applied to these problems can produce algorithms that are I O e cient This thesis adds to the growing chorus of such results The computational models we use are the external memory model and the W Stream model On the external memory model we obtain the following results 1 An I O e cient algorithm for computing