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.

Filter by
Sorted by
Tagged with
1
vote
1answer
98 views

Practical Data-oblivious Compaction?

Compaction is a particularly weak form of sorting. The problem can be phrased as follows: Given an array $A$ of $N$ cells, with at most $R$ of the cells distinguished (say by a bit), produce an array ...
2
votes
0answers
142 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
213 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
189 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
595 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
318 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
297 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 ...