Is there a linear space lower bound for streaming set equality?

Question

Consider two streams. In each stream one string arrives at a time. A query asks: Is the set of strings that has arrived so far the same in both streams?

Is there a linear space randomized lower bound for this problem?

If the sets of strings had been given in advance we could just sort them, remove duplicates, concatenate them in each set and then compute a random fingerprint of each of the two concatenated strings which can then be compared quickly using very little space (although there is of course no benefit as we first created something of linear size).

In the streaming case, we would need an updatable fingerprint it seems to do something similar. I suspect this is not possible to do in sublinear space but I don't see a proof yet.

Answer 1

There are both deterministic lower bounds and randomized upper bounds (for a version of the problem where you get check-ins and check-outs in a single stream rather than check-ins in one stream and check-outs in the other, but that makes little difference) in my paper

Space-efficient straggler identification in round-trip data streams via Newton's identitities and invertible Bloom filters. D. Eppstein, and M. T. Goodrich. arXiv:0704.3313. IEEE Trans. Knowledge and Data Engineering 23 (2): 297–306, 2011. (and WADS 2007).

See also:

What's the difference? Efficient set reconciliation without prior context. D. Eppstein, M. T. Goodrich, F. Uyeda, and G. Varghese. Proc. ACM SIGCOMM, Toronto, Canada, 2011.

which is more explicitly about comparing two sets.

In short: you can test whether two multisets (or sets with no repetitions) are the same using only very small space, or more generally find their symmetric difference in space roughly proportional to the size of the difference.

If you really mean sets, where repetitions are allowed, I think the problem may be much harder, though I don't know of a randomized lower bound for it.

Answer 2

OK, so there are a lot of ways to store sets. I don't believe that any of them give you exactly what you want for the most general case, but here are several options.

Let $S_1$ and $S_2$ be the sets, $k_1$ and $k_2$ be the number of unique elements in the sets, and $n_1$ and $n_2$ be the sum of the lengths of all elements in the sets.

General Solutions

Naive general solution in space $O(n_1+n_2)$

This solution involves keeping every string and is not time-optimized. Maintain an array of pointers to the unique strings. When a new string arrives, search through the set to see if it has already been inserted. If so, toss it, if not, insert it onto the end and resort. To check if the sets are identical, simply run through the strings in the first set, checking to make sure that each string exists in the second set. Also make sure that the size of the sets are the same. If both of these are true, then the sets are equal.

This uses space $n_1+n_2$ to store the strings and space $k_1+k_2$ to store the array of pointers, so because $k_i < n_i$, we have space $O(k_1 + k_2 + n_1 + n_2) = O(n_1 + n_2)$.

This solution is very naive and can be easily improved upon. By keeping the list sorted, one can use binary search to check for set inclusion. Set equality can be done by looping through both sets at the same time, checking for string equality.

Trie solution in space $O(n_1 + n_2)$

This solution is similar to the naive solution and also gives precise answers. Instead of sorting the elements, insert them into a trie. Depending on your strings, you may end up getting decent compression. It is possible to get almost no compression, however, so in the worst case, the space is still $O(n_1 + n_2)$. It is faster than the naive solution, however, requiring time linear to the size of the string for both insertion and set inclusion (instead of $O(x \log(x))$ time for string length $x$).

Fault-tolerant Solutions

Set of Hashes for space $O(k_1 + k_2)$

This solution is much like the general solutions, but instead of storing the set of strings, store a set of hashes. The False Positive Rate (FPR) will depend on your hashing function and the number of elements in your sets, so unfortunately, the FPR will only be bound if there is a bound on the number of unique strings. Using the trie solution, after hashing the string, set inclusion and insertion takes only constant time. Set equality takes time $O(k_1 + k_2)$.

Constant Time Set Equality

@Yonatan N mentioned this solution as a comment, but I thought I'd detail it here.

In this solution, keep the same set of hashes as the previous solution. However, for each set, also maintain a single number which is the XOR of all of the unique elements in that set. Set equality can then be checked by checking the equality of the two XOR of hashes. This operation would have only constant time and space consequences to insertion and storage.

Using a Bloom Filter

Under the assumption that you have a bound on the number of unique strings, you can use a Bloom Filter to decrease the space requirements even further. The effect of this is that you start with large space requirements $O(\text{bound on # of unique elements})$, but they never grow. This would be a good solution if you expect $k_1$ and $k_2$ to get close to your bound and want to keep your FPR guaranteed to be under a specific amount. Set equality can be done by checking to see if the bloom filters are equal (you could devise a similar constant-time equality by XORing hashes of the indexes in the Bloom Filter that are set to 1).

Others

There are other ways to do these things: Tree Sets, Windowed Sets, Stable Bloom Filters, compressing the strings, and more. Wikipedia is always your friend. Happy hunting.

Answer 3

If you can accept that no means no but yes means probably, you can do this in $O(\log n)$ bits of space, where $n$ is the number of bits in the sets.

To do so, first "collapse the universe" - use universal hash families to hash every string down to $3 \lg n$ bits. Then use polynomial hashing, which is also universal.

Answer 4

Linear space lower bound follows from the communication problem of set disjointness. See http://www.math.ias.edu/~avi/PUBLICATIONS/HastadWi2007.pdf

Answer 5

Assuming certain the hardness of certain computational problems, I think you should be able to do this in a more or less constant amount of space when you consider multisets. You can simply use a homomorphic collision resistant hash function and keep one hash digest for each stream. Everytime you see a new element, you compute its hash value, and add it to the digest for that stream (using the homomorphic properties). If the streams have been the same, so will the hash values. If the streams have not been the same, then the hash values will be different with an overwhelming probability due to the collision resistance of the hash function, since otherwise the concatenation of both streams would constitute a pair of strings that provides a collision for the hash function.

Such homomorphic hash functions can be instantiated from different widely believed computational hardness assumptions. For example, see Streaming Authenticated Data Structures (Section 3), for a lattice-based homomorphic hash function or Chameleon Hashing and Signatures for constructions based on the discrete logarithm and the factoring problem.

The only thing that slowly grows here is the hash functions output length, which depends on the length of the stream, but if your streams are poly, then you can fix it to some security/confidence parameter like 80, that is, for any two polynomially (possibly adversarially) chosen streams, the probability of a false positive is negligible in that parameter.

Answer 6

Yes, even when

n is known in advance
and
each string-length is ​ ​ $\lceil$log₂(n)$\rceil$ + 1
and
we only care about the state between updates,
not the computation required to perform updates
and
the update procedure can be non-computable

.

For all positive integers n and all elements x of {0,1}ⁿ, by
[the simpler version of the Chernoff bound], the probability of
[a random element y of {0,1}ⁿ differing from x on at most 4/9 of the positions] is at most
exp(-(2/324)$\cdot$n), which is less than 2^{-(1/113)$\cdot$n}. ​ Thus, for choosing a subset of {0,1}ⁿ whose
elements pairwise differ on more than 4/9 of the positions, each choice eliminates less than
2^n/113 of the original possibilities, so there is such a subset with more than 2^n/113 elements.


Assume n is an integer that's greater than 2, and let S be a subset of {0,1}^n-2 with more than
2^(n-2)/113 elements which is such that distinct elements of S differ on more than 4/9 of the positions,
and consider any initially-randomized algorithm whose error probability
will be at most 1/6 when the inputs are chosen as follows:

Choose s uniformly from S, and send
(0,s₀) , (1,s₁) , (2,s₂) , (3,s₃) , (4,s₄) , ... , (n-4,s_n-4) , (n-3,s_n-3) , $\star$
along both streams. ​ ​ ​ Choose m uniformly from from {0,1,2,3,4,...,n-4,n-3}
and then send $\star$ on stream 0 and (m,1) on stream 1.


The expected value, over its own possible choices of randomness for each update,
of its error probability (over the choice of input) conditioned on its own randomness,
is at most 1/6, so there is some internal randomness for which
its error probability (over the choice of input) will be at most 1/6.
Fix some such randomness for each update, giving a deterministic algorithm, which I'll call DSSEA, whose error probability on that input distribution is at most 1/6. ​ Consider a guesser G which
uses [DSSEA and DSSEA's state just before receiving the last pair of strings] as follows:

Let s' be the element of {0,1}^n-2 given by
[s'_i is DSSEA's output after sending ​ $\star$ , (i,1) ​ along streams 0,1 respectively ]. ​ ​ ​ Output the lexicographically least element of S which differs from s' on a minimum number of positions.


The expected value, over the choice of strings other than the last pair, of DSSEA's
error probability (over the choice of the last pair) conditioned on the other strings,
is at most 1/6, so the probability of that conditional probability exceeding 2/9 is at most 3/4.
Whenever that conditional probability is at most 2/9, s' will differ from s on at most
2/9 of the positions, so G will output s, since other all elements of S differ from s
on more than 4/9 of the positions, and so from s' on more than 2/9 of the positions.
Thus G has probability at least 1/4 of outputting s, so in particular has more
than $\big(\hspace{-0.03 in}$2^(n-2)/113$\hspace{-0.03 in}\big)\hspace{-0.03 in}\big/\hspace{-0.03 in}$4 possible outputs. ​ By the choice of G, that means DSSEA
has more than 2^{((n-2)/113)-2} possible internal states just before the last update.
Hardcording separate randomness for each update does not increase that number, so the initial randomized algorithm must be able to keep at least ((n-2)/113)-2 bits of state between updates.

For all integers n, if ​ 25992 < n ​ then ​ n/114 < ((n-2)/113)-2 .
For constant error rates above 1/6, just reduce the error rate
by taking a majority vote of O(1) independent parallel runs.

For

numbers M of possible strings
and
positive integers j in o(log(M))
and
error probabilities bounded above by ​ 1$\hspace{-0.04 in}\big/\hspace{-0.04 in}\big(\hspace{-0.04 in}$M^(1+Ω(1))/j$\hspace{-0.03 in}\big)$

, one can similarly get an asymptotic lower bound of ​ ​ ​ $\big(\hspace{-0.04 in}\lfloor \hspace{-0.03 in}$log₂(M choose n-1)$\rfloor$ - 1$\hspace{-0.04 in}\big)$ ​ / ​ (2$\cdot$j - 1) ​ ,
although I have neither tried working out whether-or-not that dependence on j should
be within a constant factor of tight nor tried bounds for other parameter regimes.