CS 229r: Algorithms for Big Data Fall 2015

Today we’re starting a completely new topic, which is the external memory model, also known as the disk access model. One of the earliest works on this was by Aggrawal and Vitter [1]. We’ve talked about streaming, which is where we cannot store all of the data. Here we imagine instead that our data cannot fit inside RAM, but we can store it in some other disk space. We assume that disk is infinite, but memory is finite. In the RAM, we assume that memory of size M is divided into pages of size B, i.e. there are M/B pages. The unit here is arbitrary, each item takes up constant size. Similarly, there are infinite pages of size B on disk. When we do memory I/O, we imagine that the cost is free, but when we do disk I/O, we imagine that we can fetch a page, which has a unit cost. This makes practical sense since memory is orders of magnitude faster than hard drive space, and is often far smaller. Hard drives are usually much faster when reading sequentially, which is why we use the idea of pages. In terms of exact numbers, hard drives support somewhere around 140MB/sec of sequential reads/writes, but only 120I/O’s/sec when doing reads/writes on random 4KB chunks. This is because the disk must physically spin to the read/write location. RAM supports somewhere around 5-10GB/sec of reads/writes, with much less penalty for random access. SSDs/Flash is somewhere in the middle, but with the issue that each index can only be written to a limited number of times. In the future, we’ll work with the idea of algorithms that work even without knowing the exact values of M and B, which are known as cache-oblivious algorithms