I wrote it in a hurry. O(n^4) is only for the size of the current chunk of data being operated on, usually measured in cache lines. I guess it should have been m, as n is usually used for the total input size. It's not unusual to see O(m^c * log n) algorithms or even O(m^c * log log n) if you can use vEB search structure, where m is the number of cache lines the algorithm works on, c is an algorithm specific constant, and n is the total input size.
Ah, OK. So you meant space overhead in practical terms
I would think that a greater than constant time overhead would not be compatible with a real time streaming operation. just a guess, though.
Thanks for mentioning http://en.wikipedia.org/wiki/Van_Emde_Boas_tree as I hadn't heard of that. The last paragraph on the page gives some nice pointers (use a trie or randomized hash table).
