An Introduction to Cache-Oblivious Data Structures
Trivia: Why they are called "cache-oblivious" and not "cache-aware"?<p>The paper that coined the term is here: <a href="http://cacs.usc.edu/education/cs653/Frigo-CacheOblivious-FOCS99.pdf" rel="nofollow">http://cacs.usc.edu/education/cs653/Frigo-CacheOblivious-FOC...</a><p>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.<p>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.