Space Consciousness

I was away for a week at the Workshop on Space-Conscious Algorithms at Bertinoro. The meeting brought together algorithmicists interested in streaming and cache-oblivious algorithms, and succinct data structures.

Phil Gibbons spoke about open problems, in particular, in modeling parallel, multi-level caches. He also mentioned that "systems research is about making the common cases faster" and sought algorithmic analyses that reflected it. Piotr Indyk spoke about new developments in approximate nearest neighbors, including random projections onto two and higher dimensional spaces (rather than the line as in many previous papers) and use of the Leech lattice. Martin Farach-Colton argued that cache-obliviousness really should be about disk-obliviousness. He also (tongue-in-cheek) suggested the need to forego "motivations" in theory papers that were mainly marketing and not reality. This released a lot of speakers who followed from the burden of explaining the motivation for their work! :) On the other hand, Andrew McGregor, in response to some adversarial ribbing about the random-order stream model, presented a very nice motivation for studying it, namely, that it fits neatly the study of statistical problems that take random samples of the underlying distribution. Frank Ruskey's subset encoding result was talked about in compression results.

Wolfgang Tyler of the European Patent & Trademarks Office gave a talk on building suffix arrays for searching full-text patent documents. He gave a nice motivation for going beyond reverse index with just the words to build a suffix array that looks at subwords: in German, words are concatenated to form larger words and during prior art search, one often searches for only parts of words. Martin Strauss spoke about his recent results in Compressed Sensing that improve the decoding time of the results of Donoho, Candes and Tao, Vershynin and Rudelphson, and others. Petros Drineas and Michael Mahoney spoke about my work with them on matrix low-rank approximations among other things; there is so much work in this area, just wait for their tutorial at VLDB and elsewhere. Alex Lopez-Ortiz spoke about a new performance measure that in theory showed the superiority of LRU for online caching which has been previously observed in practice: the proof technique of bisimulation seemed interesting.

Graham Cormode and Amit Chakrabarti presented streaming algorithms for biased quantiles and entropy estimation, and together with Andrew McGregor, ended up improving some of the bounds for the entropy estimation, I hear. Unfortunately I missed some of the other talks because of (a) interesting puzzles and (b) catching up with people.

There are a lot of reasons to go to these workshops (next one on Massive Data Sets, at Stanford this week). Phil Gibbons pointed out that I was a coauthor on so many results presented in the workshop, but I was busy learning about the more than the 50% of the results I did not already know! On a selfish note, I learnt that my O(n) time in-place integer sorting result from a couple of months ago may be of some interest after all.