AbstractWe 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 (log\log 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 2Omega(sqrt(log n)) in the worst case.
Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems; H.3.3 [Information Storage and Retrieval]: Information Search and Retrieval
Additional Key Words and Phrases: deterministic dynamic dictionary, membership, worst-case, trade-off
Selected references
- Arne Andersson. Faster deterministic sorting and searching in linear space. In 37th Annual Symposium on Foundations of Computer Science, pages 135-141, Burlington, Vermont, 14-16 October 1996. IEEE.
- J. Lawrence Carter and Mark N. Wegman. Universal classes of hash functions. Journal of Computer and System Sciences, 18(2):143-154, April 1979.
- Martin Dietzfelbinger, Anna Karlin, Kurt Mehlhorn, Friedhelm Meyer Auf Der Heide, Hans Rohnert, and Robert E. Tarjan. Dynamic perfect hashing: Upper and lower bounds. SIAM Journal on Computing, 23(4):738-761, August 1994.
- Michael L. Fredman, János Komlós, and Endre Szemerédi. Storing a sparse table with O(1) worst case access time. Journal of the ACM, 31(3):538-544, July 1984.
- Michael L. Fredman and Dan E. Willard. Surpassing the information theoretic bound with fusion trees. Journal of Computer and System Sciences, 47(3):424-436, December 1993.
- Peter Bro Miltersen. Error correcting codes, perfect hashing circuits, and deterministic dynamic dictionaries. In Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 556-563, San Francisco, California, 25-27 January 1998.
- Andrew Chi-Chih Yao. Should tables be sorted? Journal of the ACM, 28(3):615-628, July 1981.