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

Improve this question
$\endgroup$
8
  • 2
    $\begingroup$ Is there a reason that a hash table wouldn't do the trick? $\endgroup$
    – Dave
    Commented Jul 17, 2011 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
    Commented Jul 17, 2011 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
    Commented Jul 17, 2011 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
    Commented Jul 17, 2011 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
    Commented Jul 17, 2011 at 15:19

2 Answers 2

Reset to default
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$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ This looks fantastic. (You'll understand if I read the paper before accepting, though, right?) $\endgroup$
    – Charles
    Commented Jul 18, 2011 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.

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

Your Answer

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

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