List Ranking
Paolo Ferragina · Cambridge University Press eBooks · 2023
This chapter addresses a problem related to lists, the basic data structure underlying the design of many algorithms that manage interconnected items. It starts with an easy-to-state but I/O-inefficient solution derived from the optimal one designed for the classic RAM model; it then discusses increasingly sophisticated solutions that are elegant and efficient in the two-level memory model, and are still simple enough to be implemented with a few lines of code. The treatment of this problem will also allow us to highlight a subtle relation between parallel computation and I/O-efficient computation, which can be deployed to derive efficient disk-aware algorithms from efficient parallel algorithms.