What would be the most space-efficient way to represent a multiset (a set that can contain duplicates) using a (static) bit string (bit vector, bit array, etc.)? All of the elements in the multiset would be integers from a limited range.

My current approach is to find the greatest frequency and allocate that number of bits to each element (i.e the multiset [0,1,1,2,3,3,3,3,4] becomes 1000 1100 1000 1111 1000), but this is rather inefficient.

For reference, the larger problem is that I want to securely calculate the intersection between two multisets, so I pretty much need each bit to correspond to an element. I also need two parties to be able to build a bit string where each bit corresponds to the same element without giving away much information in the process.

  • $\begingroup$ That's obviously not optimal, since it is in effect encoding the count for each possible element as a fixed-length unary number; using a fixed-length binary encoding would reduce the space requirement for each element from $k$ to $log k$ with no additional cost. $\endgroup$ – rici Feb 11 '17 at 1:39
  • $\begingroup$ I suspect the issue here is that data structure design isn't orthogonal from design of the cryptographic intersection protocol. We can tell you how to build a space-efficient data structure in isolation, but you also have some requirements that are imposed by your desire for an efficient crypto protocol, and those requirements don't seem clearly enough stated for us to know what the requirements / evaluation criteria are. You might not be able to design the data structure in isolation -- you might need to co-design the data structure and protocol, together. $\endgroup$ – D.W. Feb 11 '17 at 17:44
  • $\begingroup$ My goal is to turn each multiset into a bit vector and use homomorphic encryption to to calculate their inner product. This is why I need two parties to be able to build bit vectors where each bit corresponds to the same element in both vectors, however they shouldn't disclose much (if any) information in the creation of these vectors. I can't think of any requirements beyond that, but if any other information would be helpful, please let me know. $\endgroup$ – Chris H. Feb 11 '17 at 23:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.