I am trying to find as many pairs of elements as possible from two distinct data streams, while being constrained by the number of elements I can hold in memory at any given time. Once a pair of elements is found, it can be removed from memory.

This problem feels like a streaming variant of the maximum coverage problem, except that I'm trying to figure out the optimal strategy for determining which elements I should keep and which ones I should prune when a new element arrives and my data structure is at its maximum capacity.

More generally, I would like to find which classical problem this can be reduced to.

A more formal phrasing of my question would be : given two streaming multisets of integers $S_1$ and $S_2$ and a positive integer capacity $C$, what is the optimal strategy to find the maximum number of pairs of identical integers from $S_1$ and $S_2$ such that at any point, the number of integers in memory is less than $C$ ?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.