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

15
votes
2answers
502 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
268 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
269 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 ...