11
$\begingroup$

I'm looking for a space-efficient data structure that holds sets (no repetition) of wordsize elements and supports fast insertion (amortized O(1)). By "space-efficient" I mean, ideally, $n + o(n)$ words to store $n$ elements.

Being a set is an important part of the question: if each element is added $\log n$ times the space used can't be $n\log n$.

The structure should also support listing its elements (reasonable efficiently); any sane structure should have no trouble here. (Fast membership queries are a plus.)

$\endgroup$
  • 2
    $\begingroup$ Is there a reason that a hash table wouldn't do the trick? $\endgroup$ – Dave Jul 17 '11 at 5:28
  • $\begingroup$ @Dave: I don't think of that as meeting the space requirement, but I suppose a sufficiently strict dynamic resizing schedule could make it work. But generally I'd like to see what's out there before actually writing code. $\endgroup$ – Charles Jul 17 '11 at 6:01
  • 1
    $\begingroup$ To get amortized $O(1)$ with dynamic resizing, you have to increase the size by a constant fraction, which I don't think meets the space requirement if you want to strictly meet $n+o(n)$. $\endgroup$ – Dave Jul 17 '11 at 7:22
  • $\begingroup$ OK, this is a bit silly—but given that your universe is of constant size (wordsize elements), even a full bit vector would have a size of $O(1)$… $\endgroup$ – Magnus Lie Hetland Jul 17 '11 at 12:47
  • $\begingroup$ @Magnus: I guess that it is meant that the actual functions behind the O- and o-notations in the question do not depend on the word size. $\endgroup$ – Tsuyoshi Ito Jul 17 '11 at 15:19
10
$\begingroup$

I think Raman and Rao's "Succinct Dynamic Dictionaries and Trees" meets the bounds you specify. From the abstract:

We first give a representation of a set $S \subseteq U = \{0, \dots , m − 1\}, |S| = n$ that supports membership queries in $O(1)$ worst case time and insertions into/deletions from $S$ in $O(1)$ expected amortised time. The representation uses $B + o(B)$ bits, where $B = \lceil lg \binom{m}{n} \rceil$ is the information-theoretic minimum space to represent $S$.

$\endgroup$
  • $\begingroup$ This looks fantastic. (You'll understand if I read the paper before accepting, though, right?) $\endgroup$ – Charles Jul 18 '11 at 13:42
1
$\begingroup$

If your application can tolerate some false positives, then you should look into using a Bloom filter.

Paraphrase of Wikipedia: A Bloom filter is a space-efficient probabilistic data structure that is used to test whether an element is a member of a set. False positives are possible, but false negatives are not. Elements can be added to the set, but not removed. The more elements that are added to the set, the larger the probability of false positives.

$\endgroup$
  • $\begingroup$ Mine can't, but +1 for a great data structure. $\endgroup$ – Charles Jul 18 '11 at 13:36

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.