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
0 votes
0 answers

Deamortization of basic COLA (Cache oblivious lookahead array)

I am reading the paper titled Cache Oblivious Streaming B-trees. I am trying to understand the deamortization technique used for basic COLA. The paper says that for every level k, for deamortization, ...
debasishg's user avatar
1 vote
2 answers

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 ...
Mark's user avatar
  • 948
2 votes
0 answers

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 ...
senseiwa's user avatar
  • 185
4 votes
2 answers

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, ...
senseiwa's user avatar
  • 185
3 votes
2 answers

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 ...
ngub05's user avatar
  • 141
15 votes
2 answers

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 ...
SamM's user avatar
  • 1,685
9 votes
2 answers

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 ...
templatetypedef's user avatar
6 votes
1 answer

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 ...
jbapple's user avatar
  • 11.2k