Deterministic Dictionaries

✍ Scribed by Torben Hagerup; Peter Bro Miltersen; Rasmus Pagh

• Book ID: 102574576
• Publisher: Elsevier Science
• Year: 2001
• Tongue: English
• Weight: 133 KB
• Volume: 41
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.2001.1171

✦ Synopsis

It is shown that a static dictionary that offers constant-time access to n elements with w-bit keys and occupies O n words of memory can be constructed deterministically in O n log n time on a unit-cost RAM with word length w and a standard instruction set including multiplication. Whereas a randomized construction working in linear expected time was known, the running time of the best previous deterministic algorithm was n 2 . Using a standard dynamization technique, the first deterministic dynamic dictionary with constant lookup time and sublinear update time is derived. The new algorithms are weakly nonuniform; i.e., they require access to a fixed number of precomputed constants dependent on w. The main technical tools employed are unit-cost error-correcting codes, word parallelism, and derandomization using conditional expectations.