ALCOMFT-TR-01-68

Rasmus Pagh
A Trade-Off For Worst-Case Efficient Dictionaries
Århus. Work package 4. May 2001.

Abstract: We consider dynamic dictionaries over the universe U={0,1}^w on a unit-cost RAM with word size w and a standard instruction set, and present a linear space deterministic dictionary accommodating membership queries in time (loglog n)^O(1) and updates in time (log n)^O(1), where n is the size of the set stored. Previous solutions either had query time (log n)^Omega(1) or update time 2^{omega(\sqrt{log n})} in the worst case.

Postscript file: ALCOMFT-TR-01-68.ps.gz (119 kb).