Why make it cache-oblivious?
n Performance of BWT heavily dependent
on cache behavior (Seward ’00)
n Avoid slowdown for large files with high
degree of repetitiveness
n Especially useful in applications like
bzip2 that are required to perform well
on different memory hierarchies