Computer Science – Data Structures and Algorithms
Scientific paper
2005-12-20
Computer Science
Data Structures and Algorithms
14 pages. Full version of a paper accepted to LATIN'06
Scientific paper
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 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.
Demaine Erik D.
der Heide Friedhelm Meyer auf
Pagh Rasmus
Patrascu Mihai
No associations
LandOfFree
De Dictionariis Dynamicis Pauco Spatio Utentibus does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with De Dictionariis Dynamicis Pauco Spatio Utentibus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and De Dictionariis Dynamicis Pauco Spatio Utentibus will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-421960