Cache-oblivious algorithms perform within a constant factor of the least possible number of memory transfers. They are analyzed on the ideal-cache model which assumes no knowledge of the parameters of the memory hierarchy.

learn more… | top users | synonyms

2
votes
0answers
73 views

Extended version of the paper “Consistent Hashing and Random Trees” with proofs

I've been reading the following paper: David Karger, Eric Lehman, Tom Leighton, Rina Panigrahy, Mathew Levine, Daniel Lewin, "Consistent Hashing and Random Trees: Distributed Caching Protocols for ...
15
votes
2answers
548 views

Exponential Speedup in External Memory

Background The external memory, or DAM model, defines the cost of an algorithm by the number of I/Os it performs (essentially, the number of cache misses). These running times are generally given in ...
9
votes
2answers
273 views

Starting point for cache-oblivious algorithms?

I'm interesting in learning more about cache-oblivious algorithms and data structures, but there are so many papers out there that I honestly don't know where to start. I've found Prokup's original ...
6
votes
1answer
284 views

Simple and cache-oblivious tries on fixed-length strings

Is there a simple and cache-oblivious data structure that solves the dynamic predecessor problem for strings of length exactly $k$ over an alphabet $A$ in worst-case $O((k\log A)/B + \log n)$ memory ...