4
$\begingroup$

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]

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.

$\endgroup$
1
$\begingroup$

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".

For deterministic dictionaries, the best known bounds are discussed in Thorup's "Mihai Pǎtraşcu: Obituary and Open Problems"

$\endgroup$
  • $\begingroup$ Sorry, I just updated the question to show I'm seeking a deterministic dictionary. $\endgroup$ – Chao Xu Dec 12 '13 at 15:54
  • $\begingroup$ 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. $\endgroup$ – Chao Xu Dec 12 '13 at 16:34
  • $\begingroup$ They frequently have size $O(n \lg m)$. Do you want the space to not include any factor of $n$? $\endgroup$ – jbapple Dec 12 '13 at 16:42
  • $\begingroup$ Sorry, that's supposed to be $O(n \lg U)$. $\endgroup$ – jbapple Dec 12 '13 at 16:51
  • $\begingroup$ 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. $\endgroup$ – Chao Xu Dec 12 '13 at 16:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.