Note: I haven't read the paper and have to admit I'm baffled how it can be sublinear given you need to store everything in there. It even claims sub-linear space too. Isn't that "magic", or am I just misunderstanding what they mean here?
I'm hoping someone closer to the field of BWTs can cast some light, but colour me sceptical!
Edit: I suppose you could have something that takes n + 10^12 n/log(n) and claim for all practical sizes of n the sub-linear part is dominant in time, but it's still really O(n) at heart. Or alternatively it's sub-linear on a specific type of data, such as sorted strings. I guess I'll just have to read it!