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.