Algorithms and Data Structures for External Memory (Foundations and Trends

by Jeffrey Scott Vitter

Data sets in large applications are often too massive to fit completely inside the computer's internal memory. The resulting input/output communication (or I/O) between fast internal memory and slower external memory (such as disks) can be a major performance bottleneck. Algorithms and Data Structures for External Memory surveys the state of the art in the design and analysis of external memory (or EM) algorithms and data structures, where the goal is to exploit locality in order to reduce the I/O costs. A variety of EM paradigms are considered for solving batched and online problems efficiently in external memory. Algorithms and Data Structures for External Memory describes several useful paradigms for the design and implementation of efficient EM algorithms and data structures. The problem domains considered include sorting, permuting, FFT, scientific computing, computational geometry, graphs, databases, geographic information systems, and text and string processing. Algorithms and Data Structures for External Memory is an invaluable reference for anybody interested in, or conducting research in the design, analysis, and implementation of algorithms and data structures.

174 pages, Paperback

First published June 9, 2008

Reviews

[Carter · Rating 2 out of 5]

The book reads like a succinct literature review which is both good and bad. Good in that the references can be found in most cases and bad in the sense that the book basically makes not much sense without looking through them since the main arguments/algorithms/proofs aren't summarized. I think given what the book costs, it's not good value. I have higher expectations more in line with a textbook given the price.