Storing the stream in less space

Question

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.

Answer 1

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