How is recursive subdivision leading to cache-oblivious algorithms practically performed? [migrated]
From wikipedia: "Typically, a cache-oblivious algorithm works by a recursive divide and conquer algorithm, where the problem is divided into smaller and smaller subproblems. Eventually, one reaches a ...
Background The external memory, or DAM model, defines the cost of an algorithm by the number of I/Os it performs (essentially, the number of cache misses). These running times are generally given in ...
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 ...
Is there a simple and cache-oblivious data structure that solves the dynamic predecessor problem for strings of length exactly $k$ over an alphabet $A$ in worst-case $O((k\log A)/B + \log n)$ memory ...