0
$\begingroup$

Question

I have a set of sets. Each set is unbounded.

I would like to find a methodology to encode (vectorize) each subset.

I am more specifically interested in memory efficient solutions.

Example

Let `X` be the superset and `A` and `B` be subsets.

$$X = \{A, B\}$$ $$A = \{1,2,3\}$$ $$B = \{2,3,4\}$$

A simple methodology to encode would be to use one-hot encoding:

$$\vec A = [1, 1, 1, 0]$$ $$\vec B = [0, 1, 1, 1]$$

Issue

Now my issue is when the subsets are large, one-hot encoding can be unrealistic. (10-30 thousand Sparse vector of unique values).

Any suggestions on encoding the inputs into a more dense vector would be appreciated.

$\endgroup$
2
  • $\begingroup$ what do you mean by encoding of unbounded set? say, how would you encode a set of integers? i.e. all integers $[0,\infty]$ $\endgroup$ – Aksakal Mar 11 '20 at 21:57
  • $\begingroup$ How large is $X$ and how large are the subsets? Do you really only care about the memory taken-up by storing the subsets, or do you want to be able to perform calculations on the subsets quickly as well? Easy case is that X is large compared to the size of the subsets and you only care about storage space: in that case, just write the subset as a bit-vector as proposed in your question, then compress it (e.g. on a computer: gzip). $\endgroup$ – Creosote Mar 14 '20 at 13:43
0
$\begingroup$

There are $2^n$ possible subsets given $n$ elements. If all of these subsets are possible, then your vector must be able to account for all of these possibilities. Thus, given no other information, it is not possible to use less than $\log_2 2^n=n$ bits to encode if your code is of fixed length. Using a variable length code can save you some memory. For example, just use $[0]$ to denote $[0,0,\ldots,0]$, and $[1]$ to denote $[0, \ldots, 0, 1]$. If you know some of the subsets are more likely than others, you can have a code where the shorter length codes are assigned to the most frequent subsets. See e.g. https://en.wikipedia.org/wiki/Variable-length_code

$\endgroup$

Your Answer

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

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