Let us have a set $S$ and a subset $T \subseteq S$. I want to find an approximate representation of $T$, i.e. I want to represent (exactly) a set $T'$ that is close to $T$. That is, I want the symmetric difference $|T \triangle T'| \leq \epsilon |T|$. I want the representation to be as small as possible.

Formally speaking, I want to have functions $f: 2^S \rightarrow \{0,1\}^*$ and $g: \{0,1\}^* \rightarrow 2^S$ such that $f(T)$ has as few bits as possible (i.e. it is as slowly growing a function of $|T|$ as possible) and $g^{-1}(f(T)) \triangle T \leq \epsilon |T|$.

If I was fine with an error of $\epsilon |S|$ then I could use a bloom filter or one of the similar data structures. However, I am not aware of similar data structures for "relative" approximation. I suspect that nothing non-trivial is possible unless $|T| \approx |S|$. But is this correct?

  • $\begingroup$ Have you looked at the filter lower bound of $\log_2 (1/\epsilon)$? That might show a lower bound for your scenario, as well. $\endgroup$
    – jbapple
    Commented Jan 17, 2022 at 15:54
  • $\begingroup$ Good point. I removed that part. $\endgroup$ Commented Jan 18, 2022 at 9:46
  • 1
    $\begingroup$ @EmilJeřábek no, I just care about information-theoretic feasibility. $\endgroup$ Commented Jan 18, 2022 at 19:58
  • 2
    $\begingroup$ I think, by, say, Turan's theorem, letting $n=|S|$, for all $k\le n/4$ and $\epsilon\le 1/4$, you can find a collection $I$ of size-$k$ subsets of $S$ such that every pair $T, T'\in I$ has Hamming distance at least $2\epsilon k$, and $I$ has size at least $\exp(\Theta(k\log n/k))$. No two sets $T, T'$ in $I$ can have $f(T)=f(T')$, implying that any $f$ must have at least $\exp(\Theta(k\log n/k))$ distinct outputs for these sets, so that most sets $T$ in $I$ have $|f(T)| = \Omega(k\log n/k)$. So you can save at best an $O(1)$ factor compared to representing all size-$k$ sets naively. $\endgroup$
    – Neal Young
    Commented Jan 18, 2022 at 23:21
  • 1
    $\begingroup$ BTW is there something "non-trivial possible" when $|T|\approx |S|$? (One trivial thing seems to be to represent $T$ via the complement $S\setminus T$, so I don't see why $|T|\approx |S|$ is much different than $|T| \ll |S|$.) $\endgroup$
    – Neal Young
    Commented Jan 19, 2022 at 0:16


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.