Techniques are provided for multiset encoding and evaluation. One method comprises encoding a multi set comprised of entities as a product of a prime number assigned to each entity in the multiset to obtain an integer representation of the multiset; adding a first entity to the multiset by multiplying the integer representation of the multiset by the prime number assigned to the first entity; removing a second entity from the multiset by dividing the integer representation of the multiset by the prime number assigned to the second entity; and identifying the entities in the multi set by decomposing the integer representation into a product of the prime numbers assigned to each of the entities in the multiset. The entities in the multiset can be, for example, devices that a given user was connected to at the given time; and/or the users connected to a given device at the given time.