# Storing the stream in less space

Suppose that a stream of data is arriving like $(4,5) (5,6), \cdots ,(7,8)$, where for each particular tuple $(a,b)$, we have $a \in [n]$ and $b \in [k]$. I want to store this stream. In my setting $k = O(n^2)$, and there are no duplicates, so the stream has at most $nk$ pairs.

I want a data structure that supports three operations:

• Insert$(a,b)$, for $a \in [n]$ and $b \in [k]$, adds the pair $(a,b)$ to the stream

• Search$(a,b)$, for $a \in [n]$ and $b \in [k]$, checks whether the pair $(a,b)$ is in the stream

• Delete$(a,b)$, for $a \in [n]$ and $b \in [k]$, removes $(a,b)$ from the stream.

I don't need to preserve the order of the stream. I'm looking for a data structure where each operation should take $O(1)$ time. Also I want the space usage to be at most $O(n)$ bits of space. It is OK if the data structure is probabilistic.

• no, I'd like to understand the question so I can try to answer it. Please don't use "EDIT:"; instead revise the question to read well for someone who encounters it for the first time. See cs.meta.stackexchange.com/q/657/755. I've taken the liberty of editing it for you; check to see if I correctly captured your question. – D.W. Sep 29 '17 at 5:22
• It appears this has nothing to do with a stream, and you just want a set data structure. There are standard data structures for storing a set, which you can explore (hash tables, bloom filters, etc.). The unusual aspect is that you want a probabilistic data structure, though you don't say what you mean by "probabilistic", so it's not entirely clear to me what the requirements are. Anyway, I don't think these requirements are going to be achievable; $O(n)$ bits of space doesn't seem enough, especially when you want to support deletion. – D.W. Sep 29 '17 at 5:27

Unfortunately you will always need space $\Omega(nk)$ to support your operations.
Consider all possible contents of your stream, i.e. all subsets of $[n]\times [k]$. There are $2^{nk}$ such subsets. Take two different subsets out of this, lets say $M$ and $M'$. Since the sets are different, there is an element $(a,b)$ which is contained in $M$ but not in $M'$ or the other way around. Now we perform the operation $\mathrm{Search}(a,b)$, for which the answer should be "Yes" for $M$ and "No" for $M'$ (or vice versa). It follows that both sets need a different storage content.
Moreover, this shows that each data structure needs a different storage content for each of the subsets. It follows that each data structure needs $\Omega(nk)$ bits of space to perform your operations (even without the delete operation and without constant time querying).