Algorithms and data structures for memory hierarchies

在越来越多的应用领域，收集和分析大量数据，以提取战略业务决策所需的信息，并做出新的科学发现。 例如，沃尔玛的PB级客户交易数据库，为谷歌搜索引擎提供动力的大量网页索引，通过现代测序技术收集和分析大量基因组数据，以及使用激光雷达技术和卫星图像构建大量高度详细的地理模型。 这些海量数据为以前无法想象的新发现提供了巨大的机会，但是从这些数据集中提取有用的信息需要能够处理它们的计算工具。 拟议的研究将导致算法，形成这种工具的心脏，即算法，有效地利用高速缓存，以加快处理数据集的大小超过主内存。 它侧重于基本的图形问题和计算几何中出现的问题，在广泛的应用领域，旨在开发高缓存效率的顺序和并行算法的研究问题。 该提案的目的是获得基本的理论见解如何设计高速缓存效率的顺序和并行算法，但它也同样强调工程效率的实现开发的算法，以验证其实际用途，并使他们提供给从业者。

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.