High-performance streaming dictionary
MA Bender, M Farach-Colton, YR Fogel… - US Patent …, 2015 - Google Patents
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 …
system is presented. A high-performance dictionary data structure is defined. The dictionary …
Cache-oblivious B-trees
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 …
hierarchical memory. The data structures are independent of the parameters of the memory …
Concurrent cache-oblivious B-trees
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 …
oblivious model to a parallel or distributed setting and present three concurrent CO B-trees …
A locality-preserving cache-oblivious dynamic dictionary
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 …
proposed data structure is cache-oblivious and locality-preserving. A cache-oblivious data …
Engineering a cache-oblivious sorting algorithm
GS Brodal, R Fagerberg, K Vinther - Journal of Experimental …, 2008 - dl.acm.org
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 …
empirical methods a number of implementation issues and parameter choices for the cache …
Cache-adaptive algorithms
MA Bender, R Ebrahimi, JT Fineman… - Proceedings of the twenty …, 2014 - SIAM
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 …
apply to environments in which the amount of memory available to an algorithm can …
[PDF][PDF] Tight bounds for the partial-sums problem
M Patrascu, ED Demaine - SODA, 2004 - people-erikdemaine.csail.mit.edu
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 …
problem in the RAM and group models of computation. If elements are chosen from an …
Engineering scalable, cache and space efficient tries for strings
N Askitis, R Sinha - The VLDB Journal, 2010 - Springer
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 …
science. The efficiency of string data structures used for this task is of paramount importance …
Cache-oblivious algorithms and data structures
GS Brodal - Scandinavian Workshop on Algorithm Theory, 2004 - Springer
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 …
model as a formal model of computation for developing algorithms in environments with …