Cache Oblivious Algorithms

catonmat.net

39 pointspkrumins3 comments

Cache Oblivious Algorithms are actually fairly old, 1999 to be precise -- Harald Prokop's Master's thesis: http://supertech.csail.mit.edu/papers/Prokop99.pdf (pdf).

Tokutek uses it: http://www.tokutek.com/careers.php

wow the one guy in the world who has worse penmanship than myself :P

In all seriously, interesting topic and the text book for that course is an amazing algorithms book. My copy is certainly well used.

I'd also very highly recommend this book, but anyone looking to buy might be interested to know that the 3rd edition comes out this fall (9/30).

http://www.amazon.com/Introduction-Algorithms-Third-Thomas-C...

"It includes two completely new chapters, on van Emde Boas trees and multithreaded algorithms, and substantial additions to the chapter on recurrence (now called "Divide-and-Conquer"). It features improved treatment of dynamic programming and greedy algorithms and a new notion of edge-based flow in the material on flow networks."

Reply on news.ycombinator.com