<p>If your application can tolerate some false positives, then you should look into using a <a href="http://en.wikipedia.org/wiki/Bloom_filter" rel="nofollow">Bloom filter</a>.</p>

<p>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.</p>

CC BY-SA 3.0
2011-07-18T13:36:40.090Z
Mine can't, but +1 for a great data structure.
Charles
CC BY-SA 3.0
2011-07-18T12:18:35.953Z
2011-07-18T12:18:35.953Z
Tyson Williams
<p>I think Raman and Rao's <a href="http://www.cs.cmu.edu/afs/cs/project/aladdin/wwwlocal/compression/RR03.pdf">"Succinct Dynamic Dictionaries and Trees"</a>  meets the bounds you specify. From the abstract:</p>

<blockquote>
  <p>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$.</p>
</blockquote>

CC BY-SA 3.0
2011-07-18T13:42:18.077Z
This looks fantastic.  (You'll understand if I read the paper before accepting, though, right?)
Charles
CC BY-SA 3.0
2011-07-18T06:45:53.190Z
2011-07-18T06:45:53.190Z
jbapple
<p>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.</p>

<p>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$.</p>

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

CC BY-SA 3.0
2011-07-17T05:28:20.993Z
Is there a reason that a hash table wouldn't do the trick?
Dave
CC BY-SA 3.0
2011-07-17T06:01:13.240Z
@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.
Charles
CC BY-SA 3.0
2011-07-17T07:22:55.107Z
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)$.
Dave
CC BY-SA 3.0
2011-07-17T12:47:13.907Z
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)$…
Magnus Lie Hetland
CC BY-SA 3.0
2011-07-17T15:19:41.067Z
@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.
Tsuyoshi Ito
CC BY-SA 3.0
2011-07-17T16:31:44.330Z
@Tsuyoshi Ito: Precisely.
Charles
CC BY-SA 3.0
2011-07-17T16:32:36.107Z
@Dave: I was thinking about resizing by 100%, 90%, 85%, 82%, ...; not sure if this would work.  But it highlights my reason for asking very well, thank you.
Charles
CC BY-SA 3.0
2011-07-18T02:01:10.950Z
@Charles: Under such a scheme, the amortized insertion time would increase with the size of the table, and therefore not be constant.
Dave
<ds.data-structures>
Set data structure for efficient repeated insertions
Charles
# Set data structure for efficient repeated insertions

(Asked by: username_0 on 2011-07-17)

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

**Tags:** ds.data-structures

> **Comments:**
> **username_1**: Is there a reason that a hash table wouldn't do the trick?  
> **username_0**: @username_1: 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.  
> **username_1**: 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)$.  
> **username_2**: 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)$…  
> **username_3**: @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.  
> **username_0**: @username_3: Precisely.  
> **username_0**: @username_1: I was thinking about resizing by 100%, 90%, 85%, 82%, ...; not sure if this would work.  But it highlights my reason for asking very well, thank you.  
> **username_1**: @username_0: Under such a scheme, the amortized insertion time would increase with the size of the table, and therefore not be constant.  

---

## 2 answers

### Answer by username_5 on 2011-07-18. Score: 10 | Accepted answer

I think Raman and Rao's ["Succinct Dynamic Dictionaries and Trees"](http://www.cs.cmu.edu/afs/cs/project/aladdin/wwwlocal/compression/RR03.pdf) 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$.

> **Comments:**
> **username_0**: This looks fantastic.  (You'll understand if I read the paper before accepting, though, right?)  

---

### Answer by username_4 on 2011-07-18. Score: 1

If your application can tolerate some false positives, then you should look into using a [Bloom filter](http://en.wikipedia.org/wiki/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.

> **Comments:**
> **username_0**: Mine can't, but +1 for a great data structure.  

---

