Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

What's the best way to represent sets that support the following two operations:

  1. Insert(s, i) - adds nonnegative integer i to set s
  2. Equal(s1, s2) - Tests if s1 and s2 are the same set.

In addition, I have an upper bound on the integers added to each set. That is, I know $N$ such that $0 \le i < N$.

I'm also willing to accept that Equal is only approximate. ie Equal(s1,s2) could be true even if s1 != s2. I guess in that case I'm looking for a hash function. Does anyone know a good hash function?

We can assume that an integer is only inserted once into a set. $N$ can be about 3-5 million, and the number of sets I want to test for equality can be in the thousands.

share|improve this question

5 Answers 5

Let $F$ be a finite field with efficient procedures for addition and
multiplication and almost-uniform sampling. $\:$ Let $z$ be a field element.
(I use that letter because things will be slightly more convenient if $z$ is
the zero element, although efficient sampling means that even if one
can't find the zero of $F\hspace{-0.03 in}$, one should still be able to find a field element.)

To initialize the data structure, sample a field element $x$.
Empty sets are represented by $z$, Insert(s,i) adds $x^i$ to the representation of s,
and Equal(s1,s2) just tests if the two representing field elements are equal.
Since addition is associative and commutative, there are no false negatives. $\:$ If each integer is only inserted once into a set, then the probability of there being at least one false positive is at most
the distance from $x$'s distribution to uniform $\;+\;$ $((N\cdot \text{number of equality tests})\hspace{.02 in}/($$\hspace{-0.03 in}\operatorname{card}$$(F\hspace{.03 in})) \;\;$.

To efficiently compute $x^i\hspace{-0.04 in}$, see this paper, and either avoid the methods that involve negative
powers or make slightly stronger assumptions on $F$. $\:$ I would recommend 5.1 on page 14.

share|improve this answer
    
This assumes that there are no duplicates. Also, this is just a special case of the method of adding the outputs of a hash function. –  Yuval Filmus May 15 at 20:02
1  
See the OP: "We can assume that an integer is only inserted once into a set." $\:$ It's a quite useful special case, since it gives provable error bounds. $\;\;\;\;$ –  Ricky Demer May 15 at 20:06
    
I'm only curious: do you insert all that formatting into your posts yourself, or is some technology doing it for you? –  Juho May 15 at 21:21
    
@Juho : $\;\;\;$ I insert it all manually. $\:$ I think it would require more knowledge about LaTeX and/or this site's rendering than I have to make a program that would handle either part automatically. $\;\;\;\;\;\;\;$ –  Ricky Demer May 15 at 21:31

If you are not allowed to add the same value more than once, then the insert operation can add the hash value of $i$ to some accumulator associated with $s$, and the equality testing can compare the accumulators.

If you are allowed to add the same value twice, you can use Bloom filters.

share|improve this answer
    
Isn't a bloom filter used to represent a single set, and efficiently test membership in that set? In my problem I have multiple sets and want to test if two sets are equal. –  foobarbazquxx May 15 at 14:57
    
You'll use one Bloom filter per set. –  Yuval Filmus May 15 at 15:19
    
Why would I want to use a Bloom filter for each set, when I don't care about testing membership in the set? That seems like overkill to me. –  foobarbazquxx May 15 at 16:57
    
@foobarbazquxx : $\;\;\;$ If the data structure needs to support inserting the same value more than once to the same set, then the data structure must suffice for testing membership. $\:$ (Just use Equal(Insert(s,i),s).) $\:$ If the data structure does not need to support that (or the data structure is allowed to represent multisets instead of sets) then you can use less memory per set. $\;\;\;\;\;\;\;$ –  Ricky Demer May 15 at 18:04
    
@foobarbazquxx Bloom filters are just a different way of using hashing, generalizing Juho's approach in their answer. With the correct parameters they sound like a reasonable approach to me. –  Yuval Filmus May 15 at 18:19

Assuming $N$ is not too large, consider using a bitvector. For example, you can use a single integer type as a data structure, or an array of bits. Insertion can be done in constant time, and equality checking is very fast as well.

share|improve this answer
    
This solution works even if there are duplicate elements. Just use bitwise OR. If $N$ is large then you can replace your bitvector with a Bloom filter (in which indices are decided by applying a hash function). –  Yuval Filmus May 15 at 18:17
    
N is on the order of 3 to 5 million –  foobarbazquxx May 15 at 19:01

I'll add an additional suggestion based on @Mihai's answer to this similar cstheory.se question.

If each object in the set has a unique hash, then any commutative operation on the hashes of the members of the set will produce a decent insertion-order independent hash of the entire set. @Yuval's Bloom filters can be viewed as using the bitwise "or" operator. @Juho's approach is also using the bitwise "or" operator and the element hash is just the "one-hot" encoding of each member of the set. @Mihai is suggesting that the encoding of a member $i$ of the set be $a^i \mod p$, for some preselected $a$ that is relatively prime to $p$, and that the commutative operator be addition $\mod p$. If $p$ is larger than $N$ then the probability of a false equality between two different sets is $O(N/p)$ (according to @Mihai's answer). I'm sure that there are situations in which bitwise "xor" works as the commutative operator too.

share|improve this answer
1  
$\operatorname{lg}_2$ is strictly increasing, so the sentence involving it can be simplified. $\;$ –  Ricky Demer May 15 at 21:33

for bitvectors the number of items is not really important, 5 million bits can be stored in 1 megabyte. you should look at the total length of the biggest number or find a mapping into smaller numbers.

For comparison you can calculate the hash over this bitvector.

share|improve this answer
    
Every number between 0 and N can appear in a set, so I'm not sure what you mean by mapping into smaller numbers. If each set requires a MB bitvector and I want to have several thousand sets I'll need several GBs of memory. Unfortunately, that's too expensive, so some kind of hash seems necessary. –  foobarbazquxx May 16 at 13:35

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.