Questions tagged [cache-oblivious]

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.

2
votes
0answers
133 views

Hashtable vs cache-oblivious [closed]

I'd like to know more about real performances of data structures, in particular two families attract my interests: hash tables cache oblivious My researches didn't find any "comprehensive" (let me ...
4
votes
2answers
192 views

Ordered-file maintenance

I am studying the Advanced Data Structures material and I'd like to implement the Ordered-file maintenance data structure. I have few questions in order to start. The papers rely on a static view, ...
3
votes
2answers
166 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
570 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
296 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
294 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 ...