2008.12.17 | Else Magård

Title: Compressed Representations of Permutations, and Applications

Speake: Jérémy Barbay, Universidad de Chile

Abstract:

We explore various techniques to compress a permutation $\\pi$ over $n$ integers, takingadvantage of ordered subsequences in $\\pi$, while supporting its application $\\pi(i)$ and the application of its inverse $\\pi^{-1}(i)$ in small time. Our compression schemes yield several interesting byproducts, in many cases matching, improving or extending the best existing results on applications such as the encoding of a permutation in orderto support iterated applications $\\pi^{k}(i)$ of it, of integer functions, and of inverted lists and suffix arrays.

Joint work with Gonzalo Navarro

Host: Gerth Stølting Brodal