A method, apparatus and computer program product for storing data in a disk storage
system is presented. A high-performance dictionary data structure is defined. The dictionary …

This dissertation presents an automated system to generate highly efficient, platform-
adapted implementations of sparse matrix kernels. We show that conventional …

Although there are many advanced and specialized texts and handbooks on algorithms,
until now there was no book that focused exclusively on the wide variety of data structures …

A streaming B-tree is a dictionary that efficiently implements insertions and range queries.
We present two cache-oblivious streaming B-trees, the shuttle tree, and the cache-oblivious …

This paper presents two dynamic search trees attaining near-optimal performance on any
hierarchical memory. The data structures are independent of the parameters of the memory …

This work treats the problem of designing data-oblivious algorithms for classical and widely
used graph problems. A data-oblivious algorithm is defined as having the same sequence of …

We present the software library Stxxl that is an implementation of the C++ standard template
library (STL) for processing huge data sets that can fit only on hard disks. It supports parallel …

In this paper we explore a simple and general approach for develo** parallel algorithms
that lead to good cache complexity on parallel machines with private or shared caches. The …

A recent direction in the design of cache-efficient and diskefficient algorithms and data
structures is the notion of cache obliviousness, introduced by Frigo, Leiserson, Prokop, and …

We compare the number of cache misses M 1 for running a computation on a single
processor with cache size C 1 to the total number of misses Mp for the same computation …