Fast catenable dictionaries

Karim Douieb

The aim of this talk is to present an interesting way to approach the problem of joining two dictionaries while maintaining fast access to the elements. We will show a simple join algorithm with O(1) amortized cost and we will also present a more complicated join algorithm with O(1) worst-case cost. (This work is in progress so be ready for a messy talk.)