<p>Let us have a set <span class="math-container">$S$</span> and a subset <span class="math-container">$T \subseteq S$</span>. I want to find an approximate representation of <span class="math-container">$T$</span>, i.e. I want to represent (exactly) a set <span class="math-container">$T'$</span> that is close to <span class="math-container">$T$</span>. That is, I want the symmetric difference <span class="math-container">$|T \triangle T'| \leq \epsilon |T|$</span>. I want the representation to be as small as possible.</p>
<p>Formally speaking, I want to have functions <span class="math-container">$f: 2^S \rightarrow \{0,1\}^*$</span> and <span class="math-container">$g: \{0,1\}^* \rightarrow 2^S$</span> such that <span class="math-container">$f(T)$</span> has as few bits as possible (i.e. it is as slowly growing a function of <span class="math-container">$|T|$</span> as possible) and <span class="math-container">$g^{-1}(f(T)) \triangle T \leq \epsilon |T|$</span>.</p>
<p>If I was fine with an error of <span class="math-container">$\epsilon |S|$</span> then I could use a bloom filter or one of the similar data structures. However, I am not aware of similar data structures for &quot;relative&quot; approximation. I suspect that nothing non-trivial is possible unless <span class="math-container">$|T| \approx |S|$</span>. But is this correct?</p>

CC BY-SA 4.0
2022-01-17T15:54:00.163Z
Have you looked at the filter lower bound of $\log_2 (1/\epsilon)$? That might show a lower bound for your scenario, as well.
jbapple
CC BY-SA 4.0
2022-01-18T09:46:06.037Z
Good point. I removed that part.
user2316602
CC BY-SA 4.0
2022-01-18T11:57:42.367Z
Do you have any efficiency requirements on $f$ and $g$?
Emil Jeřábek
CC BY-SA 4.0
2022-01-18T19:58:03.127Z
@EmilJeřábek no, I just care about information-theoretic feasibility.
user2316602
CC BY-SA 4.0
2022-01-18T23:21:27.773Z
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.
Neal Young
CC BY-SA 4.0
2022-01-19T00:16:13.773Z
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|$.)
Neal Young
CC BY-SA 4.0
2022-01-24T22:55:29.807Z
For me I would like to say that for smaller $T$, say $|T|\le |S|/3$ you can just keep $T$ at it is, for larger you can use the technique of $\varepsilon/3|S|$. By a lot of inequality, the number of sets that $\le  |S|/3$ is an exponentially fraction of all the sets.
JetfiRex
<ds.data-structures><it.information-theory><coding-theory>
Approximate (in hamming distance) subset representation
user2316602
# Approximate (in hamming distance) subset representation

(Asked by: username_0 on 2022-01-17)

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?

**Tags:** ds.data-structures, it.information-theory, coding-theory
> **Comments:**
> **username_1**: Have you looked at the filter lower bound of $\log_2 (1/\epsilon)$? That might show a lower bound for your scenario, as well.  
> **username_0**: Good point. I removed that part.  
> **username_2**: Do you have any efficiency requirements on $f$ and $g$?  
> **username_0**: @EmilJeřábek no, I just care about information-theoretic feasibility.  
> **username_3**: 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.  
> **username_3**: 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|$.)  
> **username_4**: For me I would like to say that for smaller $T$, say $|T|\le |S|/3$ you can just keep $T$ at it is, for larger you can use the technique of $\varepsilon/3|S|$. By a lot of inequality, the number of sets that $\le  |S|/3$ is an exponentially fraction of all the sets.  

---

## 0 answers

