<p>If randomness is allowed, you can get space $B + o(B)$ and time $O(1)$ (worst-case, with high probability), where $B$ is $\lg {U \choose n}$, which is the lower bound on how much space you need using <em>any</em> representation: <a href="http://arxiv.org/abs/0912.5424" rel="nofollow">Arbitman et al., " Backyard Cuckoo Hashing: Constant Worst-Case Operations with a Succinct Representation"</a>.</p>

<p>For deterministic dictionaries, the best known bounds are discussed in <a href="http://albcom.lsi.upc.edu/ojs/index.php/beatcs/article/viewFile/163/176" rel="nofollow">Thorup's "Mihai Pǎtraşcu: Obituary and Open Problems"</a></p>

CC BY-SA 3.0
2013-12-12T15:54:41.930Z
Sorry, I just updated the question to show I'm seeking a deterministic dictionary.
Chao Xu
CC BY-SA 3.0
2013-12-12T16:34:10.503Z
This and most dynamic dictionary literature are under the constraints that the space should be almost linear to the number of elements in the dictionary. I'm looking for the case when the space is a function of the size of the universe.
Chao Xu
CC BY-SA 3.0
2013-12-12T16:42:13.917Z
They frequently have size $O(n \lg m)$. Do you want the space to not include any factor of $n$?
jbapple
CC BY-SA 3.0
2013-12-12T16:51:33.967Z
Sorry, that's supposed to be $O(n \lg U)$.
jbapple
CC BY-SA 3.0
2013-12-12T16:58:42.220Z
Yes, I like space of the form $O(U^{1/c})$ (and assume the dictionary never holds more than $U^{1/c}$ elements). The hope is that a relaxed bound can speed up the operations.
Chao Xu
CC BY-SA 3.0
2013-12-12T17:14:27.840Z
Is that $c$ in your comment the same as the one in the question? If so, then $n = O(U^{1/c})$, so dictionaries of size $O(n \lg U)$ are of size $O(U^{1/c})$.
jbapple
CC BY-SA 3.0
2013-12-12T17:33:16.283Z
True. The implication only goes in one way. Potentially there are faster known data structures for my version of the problem.
Chao Xu
CC BY-SA 3.0
2013-12-12T15:42:41.880Z
2013-12-12T16:51:00.277Z
2013-12-12T16:51:00.277Z
jbapple
<p>We want to maintain a dictionary of <span class="math-container">$m$</span> elements with insert/delete and lookup in the word RAM model. Assume <span class="math-container">$m=O(n)$</span> at all times, so there can't be too many inserts without deletions. The universe has size <span class="math-container">$\{0,\ldots,n^c-1\}$</span> for some constant <span class="math-container">$c$</span>.</p>
<p>How fast can we support these operations deterministically (in either worst case or amortized time) if we are restricted to <span class="math-container">$O(n)$</span> space? How about <span class="math-container">$O(n \mathop{\mathrm{polylog}} n)$</span> space?</p>
<p>A few simple observations:</p>
<ul>
<li><p>When <span class="math-container">$c=1$</span>, an array of size <span class="math-container">$n$</span> support all operations in worst time <span class="math-container">$O(1)$</span>.</p>
</li>
<li><p>It's not hard to come up with a <span class="math-container">$O(n^{1+\epsilon})$</span> space data structure so all queries can be done in <span class="math-container">$O(\frac{1}{\epsilon})$</span> worst case time for any <span class="math-container">$\epsilon&gt;0$</span>.</p>
</li>
<li><p>We can implement all operations in worst time <span class="math-container">$O\left(\frac{(\log \log n)^2}{\log \log \log n}\right)$</span> with <span class="math-container">$O(m)$</span> space using exponential tree.<a href="http://dl.acm.org/citation.cfm?id=335344" rel="nofollow noreferrer">[1]</a></p>
</li>
</ul>
<p>To clarify, I'm looking for dictionaries with space requirement as a function of the size of the universe, and not the number of elements in the dictionary.</p>

<ds.data-structures>
Deterministic dynamic dictionary on a small universe
Chao Xu
# Deterministic dynamic dictionary on a small universe

(Asked by: username_0 on 2013-12-12)

We want to maintain a dictionary of $m$ elements with insert/delete and lookup in the word RAM model. Assume $m=O(n)$ at all times, so there can't be too many inserts without deletions. The universe has size $\{0,\ldots,n^c-1\}$ for some constant $c$.

How fast can we support these operations deterministically (in either worst case or amortized time) if we are restricted to $O(n)$ space? How about $O(n \mathop{\mathrm{polylog}} n)$ space?

A few simple observations:

* When $c=1$, an array of size $n$ support all operations in worst time $O(1)$.
* It's not hard to come up with a $O(n^{1+\epsilon})$ space data structure so all queries can be done in $O(\frac{1}{\epsilon})$ worst case time for any $\epsilon>0$.
* We can implement all operations in worst time $O\left(\frac{(\log \log n)^2}{\log \log \log n}\right)$ with $O(m)$ space using exponential tree.[[1]](http://dl.acm.org/citation.cfm?id=335344)

To clarify, I'm looking for dictionaries with space requirement as a function of the size of the universe, and not the number of elements in the dictionary.

**Tags:** ds.data-structures

---

## 1 answers

### Answer by username_1 on 2013-12-12. Score: 1

If randomness is allowed, you can get space $B + o(B)$ and time $O(1)$ (worst-case, with high probability), where $B$ is $\lg {U \choose n}$, which is the lower bound on how much space you need using *any* representation: [Arbitman et al., " Backyard Cuckoo Hashing: Constant Worst-Case Operations with a Succinct Representation"](http://arxiv.org/abs/0912.5424).

For deterministic dictionaries, the best known bounds are discussed in [Thorup's "Mihai Pǎtraşcu: Obituary and Open Problems"](http://albcom.lsi.upc.edu/ojs/index.php/beatcs/article/viewFile/163/176)

> **Comments:**
> **username_0**: Sorry, I just updated the question to show I'm seeking a deterministic dictionary.  
> **username_0**: This and most dynamic dictionary literature are under the constraints that the space should be almost linear to the number of elements in the dictionary. I'm looking for the case when the space is a function of the size of the universe.  
> **username_1**: They frequently have size $O(n \lg m)$. Do you want the space to not include any factor of $n$?  
> **username_1**: Sorry, that's supposed to be $O(n \lg U)$.  
> **username_0**: Yes, I like space of the form $O(U^{1/c})$ (and assume the dictionary never holds more than $U^{1/c}$ elements). The hope is that a relaxed bound can speed up the operations.  
> **username_1**: Is that $c$ in your comment the same as the one in the question? If so, then $n = O(U^{1/c})$, so dictionaries of size $O(n \lg U)$ are of size $O(U^{1/c})$.  
> **username_0**: True. The implication only goes in one way. Potentially there are faster known data structures for my version of the problem.  

---

