<p>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</p>

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

<p>See also:</p>

<p>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.</p>

<p>which is more explicitly about comparing two sets.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2016-07-31T14:02:18.560Z
Thanks although it is really the randomized lower bound you mention at the end that I am interested in.
Simd
CC BY-SA 3.0
2016-07-30T22:51:15.480Z
2016-07-30T22:51:15.480Z
David Eppstein
<p>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.</p>
<p>Let <span class="math-container">$S_1$</span> and <span class="math-container">$S_2$</span> be the sets, <span class="math-container">$k_1$</span> and <span class="math-container">$k_2$</span> be the number of unique elements in the sets, and <span class="math-container">$n_1$</span> and <span class="math-container">$n_2$</span> be the sum of the lengths of all elements in the sets.</p>
<h1>General Solutions</h1>
<h3>Naive general solution in space <span class="math-container">$O(n_1+n_2)$</span></h3>
<p>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.</p>
<p>This uses space <span class="math-container">$n_1+n_2$</span> to store the strings and space <span class="math-container">$k_1+k_2$</span> to store the array of pointers, so because <span class="math-container">$k_i &lt; n_i$</span>, we have space <span class="math-container">$O(k_1 + k_2 + n_1 + n_2) = O(n_1 + n_2)$</span>.</p>
<p>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.</p>
<h3>Trie solution in space <span class="math-container">$O(n_1 + n_2)$</span></h3>
<p>This solution is similar to the naive solution and also gives precise answers.  Instead of sorting the elements, insert them into a <a href="https://en.wikipedia.org/wiki/Trie" rel="nofollow noreferrer">trie</a>.  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 <span class="math-container">$O(n_1 + n_2)$</span>.  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 <span class="math-container">$O(x \log(x))$</span> time for string length <span class="math-container">$x$</span>).</p>
<h1>Fault-tolerant Solutions</h1>
<h3>Set of Hashes for space <span class="math-container">$O(k_1 + k_2)$</span></h3>
<p>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 <span class="math-container">$O(k_1 + k_2)$</span>.</p>
<h3>Constant Time Set Equality</h3>
<p>@Yonatan N mentioned this solution as a comment, but I thought I'd detail it here.</p>
<p>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 <b>unique</b> 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.</p>
<h3>Using a Bloom Filter</h3>
<p>Under the assumption that you have a bound on the number of unique strings, you can use a <a href="https://en.wikipedia.org/wiki/Bloom_filter" rel="nofollow noreferrer">Bloom Filter</a> to decrease the space requirements even further.  The effect of this is that you start with large space requirements <span class="math-container">$O(\text{bound on # of unique elements})$</span>, but they never grow.  This would be a good solution if you expect <span class="math-container">$k_1$</span> and <span class="math-container">$k_2$</span> 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).</p>
<h1>Others</h1>
<p>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.</p>

CC BY-SA 4.0
2016-07-30T18:56:57.447Z
2019-03-13T07:56:16.667Z
2020-06-17T09:38:08.363Z
bbejot
<p>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.</p>

<p>To do so, first "collapse the universe" - use universal hash families to hash every string down to $3 \lg n$ bits. <a href="https://cstheory.stackexchange.com/a/3403/43">Then use polynomial hashing, which is also universal.</a></p>

CC BY-SA 3.0
2016-08-01T00:01:51.850Z
Are you sure about what the question is asking? From the statement "If the sets of strings had been given in advance we could just sort them, concatenate them in each set and then compute a random fingerprint of each of the two concatenated strings which can then be compared..." I got the impression that multiset equality was the problem in question.
jbapple
CC BY-SA 3.0
2016-08-01T09:21:57.673Z
It is set equality. You are right I should have said "sort and then remove duplicates" in the question.
Simd
CC BY-SA 3.0
2016-08-01T09:23:36.103Z
But I can accept either one sided or two sides error.
Simd
CC BY-SA 3.0
2016-07-31T17:08:18.317Z
2016-07-31T17:08:18.317Z
2017-04-13T12:32:28.077Z
jbapple
<p>Linear space lower bound follows from the communication problem of set disjointness. See <a href="http://www.math.ias.edu/~avi/PUBLICATIONS/HastadWi2007.pdf" rel="nofollow">http://www.math.ias.edu/~avi/PUBLICATIONS/HastadWi2007.pdf</a></p>

CC BY-SA 3.0
2016-07-27T21:31:03.913Z
2016-07-27T21:31:03.913Z
Palash Dey
<p>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. </p>

<p>Such homomorphic hash functions can be instantiated from different widely believed computational hardness assumptions. 
For example, see <a href="http://elaineshi.com/docs/streaming.pdf" rel="nofollow">Streaming Authenticated Data Structures (Section 3)</a>, for a lattice-based homomorphic hash function or <a href="https://www.semanticscholar.org/paper/Chameleon-Hashing-and-Signatures-Krawczyk-Rabin/1c294428c76ba7d1d0bb5e1d1bc931138c092453/pdf" rel="nofollow">Chameleon Hashing and Signatures</a> for constructions based on the discrete logarithm and the factoring problem.</p>

<p>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.</p>

CC BY-SA 3.0
2016-08-03T16:07:42.227Z
2016-08-03T20:52:29.817Z
2016-08-03T20:52:29.817Z
Cryptonaut
<p>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?</p>

<blockquote>
  <p>Is there a linear space randomized lower bound for this problem?</p>
</blockquote>

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

<p>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.</p>

CC BY-SA 3.0
2016-07-28T07:58:10.807Z
Is there a known upper bound on the number of possible strings?
András Salamon
CC BY-SA 3.0
2016-07-28T08:55:19.477Z
@AndrásSalamon I didn't have a firm answer to that in mind but we can assume that the number of possible stings is greater than the number of strings seen so far if that helps.
Simd
CC BY-SA 3.0
2016-07-28T14:49:37.480Z
If you come up with a sufficiently random hash function on the elements, wouldn't the xor of all hashes of strings seen so far be 0 exactly when the sets are the same (up to low probability events)? Or can each set present the same item multiple times and it's up to us to identify and ignore duplicates?
Yonatan N
CC BY-SA 3.0
2016-07-28T15:18:20.143Z
@YonatanN  I had in mind that the same string can arrive on multiple occasions at different times in a stream.
Simd
CC BY-SA 3.0
2016-07-29T08:30:12.903Z
@Lembik the reason I ask is that with a fixed upper bound the possible strings are an alphabet, and the problem is then to decide if two input bags are the same set.  This then seems amenable to techniques for two-party Equality, with bounds in terms of the number of input symbols (strings).  Without an upper bound, I'm not convinced that even a linear upper bound is possible, since one seems to have to to defeat an adversary that can pick strings that are different but have the same hashes.
András Salamon
CC BY-SA 3.0
2016-07-30T01:51:48.900Z
To clarify, by linear do you mean linear in the number of unique strings received so far or in the sum of all the lengths of those strings?
bbejot
CC BY-SA 3.0
2016-07-30T06:39:18.830Z
@bbejot I meant the former but my guess is that a tight result will have some extra lower order terms too.
Simd
CC BY-SA 3.0
2016-07-30T06:41:27.547Z
@AndrásSalamon You make a good point. I don't know the solution to either case currently so if the former is easier that seems a good start.
Simd
<cc.complexity-theory><randomized-algorithms><space-bounded>
Is there a linear space lower bound for streaming set equality?
Simd
# Is there a linear space lower bound for streaming set equality?

(Asked by: username_0 on 2016-07-26)

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.

**Tags:** cc.complexity-theory, randomized-algorithms, space-bounded

> **Comments:**
> **username_1**: Is there a known upper bound on the number of possible strings?  
> **username_0**: @AndrásSalamon I didn't have a firm answer to that in mind but we can assume that the number of possible stings is greater than the number of strings seen so far if that helps.  
> **username_2**: If you come up with a sufficiently random hash function on the elements, wouldn't the xor of all hashes of strings seen so far be 0 exactly when the sets are the same (up to low probability events)? Or can each set present the same item multiple times and it's up to us to identify and ignore duplicates?  
> **username_0**: @YonatanN  I had in mind that the same string can arrive on multiple occasions at different times in a stream.  
> **username_1**: @Lembik the reason I ask is that with a fixed upper bound the possible strings are an alphabet, and the problem is then to decide if two input bags are the same set.  This then seems amenable to techniques for two-party Equality, with bounds in terms of the number of input symbols (strings).  Without an upper bound, I'm not convinced that even a linear upper bound is possible, since one seems to have to to defeat an adversary that can pick strings that are different but have the same hashes.  
> **username_3**: To clarify, by linear do you mean linear in the number of unique strings received so far or in the sum of all the lengths of those strings?  
> **username_0**: @username_3 I meant the former but my guess is that a tight result will have some extra lower order terms too.  
> **username_0**: @AndrásSalamon You make a good point. I don't know the solution to either case currently so if the former is easier that seems a good start.  

---

## 5 answers

### Answer by username_4 on 2016-07-30. Score: 4

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.

> **Comments:**
> **username_0**: Thanks although it is really the randomized lower bound you mention at the end that I am interested in.  

---

### Answer by username_3 on 2016-07-30. Score: 3

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](https://en.wikipedia.org/wiki/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

@username_2 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](https://en.wikipedia.org/wiki/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 by username_5 on 2016-07-31. Score: 2

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.](https://cstheory.stackexchange.com/a/3403/43)

> **Comments:**
> **username_5**: Are you sure about what the question is asking? From the statement "If the sets of strings had been given in advance we could just sort them, concatenate them in each set and then compute a random fingerprint of each of the two concatenated strings which can then be compared..." I got the impression that multiset equality was the problem in question.  
> **username_0**: It is set equality. You are right I should have said "sort and then remove duplicates" in the question.  
> **username_0**: But I can accept either one sided or two sides error.  

---

### Answer by username_6 on 2016-07-27. Score: 1

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


---

### Answer by username_7 on 2016-08-03. Score: 1

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)](http://elaineshi.com/docs/streaming.pdf), for a lattice-based homomorphic hash function or [Chameleon Hashing and Signatures](https://www.semanticscholar.org/paper/Chameleon-Hashing-and-Signatures-Krawczyk-Rabin/1c294428c76ba7d1d0bb5e1d1bc931138c092453/pdf) 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.


---

