De Dictionariis Dynamicis Pauco Spatio Utentibus

Erik D. Demaine, Friedhelm Meyer auf der Heide, Rasmus Pagh +1

We develop dynamic dictionaries on the word RAM that use asymptotically optimal space, up to constant factors, subject to insertions and deletions, and subject to supporting perfec…