9
$\begingroup$

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!

Improve this question
$\endgroup$

2 Answers 2

Reset to default
7
$\begingroup$

I still find one of the original articles (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 are Erik Demaine's video lectures on c-o algos, which are also very good.

Improve this answer
$\endgroup$
6
$\begingroup$

I enjoyed the chapter on cache-oblivious data structures in the Handbook of Data Structures and Applications.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.