Abstract:
We consider dictionaries over the universe 
on a
unit-cost RAM with word size 
and a standard instruction set. We present a
linear space deterministic dictionary with membership queries in time
and updates in time
, where 
is the
size of the set stored. This is the first such data structure to
simultaneously achieve query time
and update time
on a
unit-cost RAM with word size and a standard instruction set. We present a
linear space deterministic dictionary with membership queries in time
and updates in time
, where is the
size of the set stored. This is the first such data structure to
simultaneously achieve query time
and update time
Available as PostScript, PDF.