An Introduction to Cache-Oblivious Data Structures
Trivia: Why they are called "cache-oblivious" and not "cache-aware"?The paper that coined the term is here: http://cacs.usc.edu/education/cs653/Frigo-CacheOblivious-FOC...Basically, there were first cache-aware algorithms that assumed certain cache sizes and other properties. "Cache-oblivious" algorithms were a refinement that worked well for many cache sizes.All in all it's silly that the "cache-oblivious" term was the one that survived, because now cache-unaware and cache-oblivious algorithms mean the opposite things - contradicting the dictionary definition of oblivious.