De Dictionariis Dynamicis Pauco Spatio Utentibus

Simple item page
dc.creatorDemaine, Erik D.
dc.creatorder Heide, Friedhelm Meyer auf
dc.creatorPagh, Rasmus
dc.creatorPatrascu, Mihai
dc.date2005-12-20
dc.date.accessioned2026-07-07T06:53:52Z
dc.date.available2026-07-07T06:53:52Z
dc.descriptionWe 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 Theta(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 Theta(n lglg(u/n) + n lg(n/(t+1))) bits when supporting only perfect-hashing queries, and it is Theta(n lg(u/n) + n lg(n/(t+1))) bits when also supporting membership queries. All upper bounds are new, as is the Omega(n lg(n/(t+1))) lower bound.
dc.description14 pages. Full version of a paper accepted to LATIN'06
dc.identifierhttps://arxiv.org/abs/cs/0512081
dc.identifierhttp://arxiv.org/abs/cs/0512081
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/105740
dc.subjectData Structures and Algorithms
dc.titleDe Dictionariis Dynamicis Pauco Spatio Utentibus
dc.typetext

Files

Collections

arXiv