Algorithms and data structures for memory hierarchies

In an increasing number of application areas, massive amounts of data are collected and analyzed to extract the information needed for strategic business decisions and to make new scientific discoveries. Examples include Walmart's petabyte-sized customer transaction database, a massive index of web pages powering Google's search engine, the collection and analysis of large amounts of genome data made available through modern sequencing technologies, and the construction of massive, highly detailed geographic models using LIDAR technology and satellite imagery. These massive amounts of data present tremendous opportunities for new discoveries that were previously unimaginable, but extracting useful information from such data sets requires computational tools that are capable of processing them. The proposed research will lead to algorithms that form the heart of such tools, namely algorithms that make effective use of cache memory to speed up the processing of data sets beyond the size of main memory. It focuses on fundamental graph problems and problems in computational geometry that arise in a wide range of application domains and aims to develop sequential and parallel algorithms with high cache efficiency for the studied problems. The aim of the proposal is to gain fundamental theoretical insights into how to design cache-efficient sequential and parallel algorithms, but it also places an equally strong emphasis on engineering efficient implementations of the developed algorithms, in order to verify their practical usefulness and make them available to practitioners.