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.

  • $\begingroup$ 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. $\endgroup$ – D.W. Sep 29 '17 at 5:22
  • 2
    $\begingroup$ 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. $\endgroup$ – 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).


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.