Algorithms and Data Structures for Massive Datasets

9 Introducing the external memory model

This chapter covers

• Introducing computer limitations that affect the design of data-intensive applications
• Introducing and describing the external memory model (DAM model)
• Building simple scanning, searching, and merging algorithms in external memory
• Reviewing use cases where data scientists and programmers work with huge files
• Using Big-O notation to measure I/O efficiency of the algorithms

This chapter introduces fundamental ideas that form part 3 of the book. We begin by introducing external memory algorithms and the external memory model [1]. This model will teach us how to view the efficiency of algorithms and data structures in the context of working with large datasets stored on disk.

Most applications ...