<p>I still find one of the <a href="http://ieeexplore.ieee.org/iel5/6604/17631/00814600.pdf?arnumber=814600">original articles</a> (I could also find it in Google Scholar) quite interesting and clear... in this case it is not extremely "scientific-y":</p>

<p>M. Frigo, C.E. Leiserson, H. Prokop, and S. Ramachandran. Cache-oblivious algorithms. In Proceedings of the 40th IEEE Symposium on Foundations of Computer Science (FOCS 99), p.285-297. 1999. </p>

<p>Also, <a href="http://curiousreef.com/class/introduction-to-algorithms-mit-604/lesson/15/">here</a> are Erik Demaine's video lectures on c-o algos, which are also very good.</p>

CC BY-SA 3.0
2011-06-16T14:32:30.450Z
2011-06-16T14:32:30.450Z
Dervin Thunk
<p>I enjoyed the <a href="http://www.cs.au.dk/~gerth/pub/cacheoblivious05.html">chapter on cache-oblivious data structures</a> in the Handbook of Data Structures and Applications.</p>

CC BY-SA 3.0
2011-06-16T06:19:30.547Z
2011-06-16T06:19:30.547Z
jbapple
<p>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 thesis on the subject, which seems like a good starting point, but if there's a simple and accessible introduction to the subject I'd much rather start there.  Is there a standard "go-to" reference on the subject?</p>

<p>Thanks!</p>

<ds.algorithms><reference-request><cache-oblivious>
Starting point for cache-oblivious algorithms?
templatetypedef
# Starting point for cache-oblivious algorithms?

(Asked by: username_0 on 2011-06-16)

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 thesis on the subject, which seems like a good starting point, but if there's a simple and accessible introduction to the subject I'd much rather start there. Is there a standard "go-to" reference on the subject?

Thanks!

**Tags:** ds.algorithms, reference-request, cache-oblivious


---

## 2 answers

### Answer by username_1 on 2011-06-16. Score: 7 | Accepted answer

I still find one of the [original articles](http://ieeexplore.ieee.org/iel5/6604/17631/00814600.pdf?arnumber=814600) (I could also find it in Google Scholar) quite interesting and clear... in this case it is not extremely "scientific-y":

M. Frigo, C.E. Leiserson, H. Prokop, and S. Ramachandran. Cache-oblivious algorithms. In Proceedings of the 40th IEEE Symposium on Foundations of Computer Science (FOCS 99), p.285-297. 1999.

Also, [here](http://curiousreef.com/class/introduction-to-algorithms-mit-604/lesson/15/) are Erik Demaine's video lectures on c-o algos, which are also very good.


---

### Answer by username_2 on 2011-06-16. Score: 6

I enjoyed the [chapter on cache-oblivious data structures](http://www.cs.au.dk/~gerth/pub/cacheoblivious05.html) in the Handbook of Data Structures and Applications.


---

