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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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"

Improve this answer
$\endgroup$
7
  • $\begingroup$ Sorry, I just updated the question to show I'm seeking a deterministic dictionary. $\endgroup$
    – Chao Xu
    Dec 12, 2013 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, 2013 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, 2013 at 16:42
  • $\begingroup$ Sorry, that's supposed to be $O(n \lg U)$. $\endgroup$
    – jbapple
    Dec 12, 2013 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, 2013 at 16:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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