Paper by Erik D. Demaine

Reference:

Erik D. Demaine, Friedhelm Meyer auf der Heide, Rasmus Pagh, and Mihai Pǎtraşcu, “De Dictionariis Dynamicis Pauco Spatio Utentibus (lat. On Dynamic Dictionaries Using Little Space)”, in Proceedings of the 7th Latin American Symposium on Theoretical Informatics (LATIN 2006), Valdivia, Chile, March 20–24, 2006, pages 349–361.

Abstract:

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 perfect-hashing queries and/or membership queries, each operation in constant time with high probability. When supporting only membership queries, we attain the optimal space bound of Θ(n lg (u/n)) bits, where n and u are the sizes of the dictionary and the universe, respectively. Previous dictionaries either did not achieve this space bound or had time bounds that were only expected and amortized. When supporting perfect-hashing queries, the optimal space bound depends on the range {1, 2, …, n+t} of hashcodes allowed as output. We prove that the optimal space bound is Θ(n lg lg (u/n) + n lg (n/(t+1))) bits when supporting only perfect-hashing queries, and it is Θ(n lg (u/n) + n lg (n/(t+1))) bits when also supporting membership queries. All upper bounds are new, as is the Ω(n lg (n/(t+1))) lower bound.

Length:

The paper is 12 pages.

Availability:

The paper is available in PostScript (347k), gzipped PostScript (154k), and PDF (207k).

See information on file formats.

[Google Scholar search]

Related papers:

PerfectHashing_Manuscript (De Dictionariis Dynamicis Pauco Spatio Utentibus (lat. On Dynamic Dictionaries Using Little Space))