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 …

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 …

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 paper presents concurrent cache-oblivious (CO) B-trees. We extend the cache-
oblivious model to a parallel or distributed setting and present three concurrent CO B-trees …

This paper presents a simple dictionary structure designed for a hierarchical memory. The
proposed data structure is cache-oblivious and locality-preserving. A cache-oblivious data …

This paper is an algorithmic engineering study of cache-oblivious sorting. We investigate by
empirical methods a number of implementation issues and parameter choices for the cache …

We introduce the cache-adaptive model, which generalizes the external-memory model to
apply to environments in which the amount of memory available to an algorithm can …

We close the gaps between known lower and upper bounds for the online partial-sums
problem in the RAM and group models of computation. If elements are chosen from an …

Storing and retrieving strings in main memory is a fundamental problem in computer
science. The efficiency of string data structures used for this task is of paramount importance …

Abstract Frigo, Leiserson, Prokop and Ramachandran in 1999 introduced the ideal-cache
model as a formal model of computation for developing algorithms in environments with …