I/O Model of Computation

The Rule: Dominance of I/O cost

  • The time taken to perform a disk access is much larger than the time needed for manipulating data in the main memory
  • Thus, the number of block accesses (Disk I/Os) is a good approximation to the time needed for an algorithm

Example

  • read a block is ~11 mls (see Secondary Storage#Accessing)
  • search for a tuple within a block when it's in the main memory is ~1000 instructions (even with sequential search)
  • i.e. search in the main memory is less than %1 of the block access time, can neglect it safely


Sources

Machine Learning Bookcamp: Learn machine learning by doing projects. Get 40% off with code "grigorevpc".

Share your opinion