4
$\begingroup$

I have a multiset $S$ of $n$-bit strings. Let $1_S(s)$ denote the number of times that string $s$ appears in $S$, i.e., the multiplicity of $s$ in $S$. I want to find a partition of $\{1,2,\dots,n\}$ such that the projections onto these index sets all have large multiplicities, but let me explain what I mean by that.

If $I$ is a subset of $\{1,2,\dots,n\}$ (i.e., a set of indices), then let $\rho_I(s)$ denote the projection of string $s$ onto the indices in $I$. In other words, if $I=\{i_1,i_2,\dots,i_k\}$, then $\rho_I(s)$ is the $k$-bit string $s_{i_1} \, s_{i_2} \, \cdots \, s_{i_k}$. Also, let $\rho_I(S)$ denote the multiset $\{\rho_I(s) : s \in S\}$. For instance, if $S=\{01,01,11\}$ and $I=\{2\}$, then $\rho_I(S)=\{1,1,1\}$.

We'll say that an index set $I$ is good if every element $t$ of $T=\rho_I(S)$ has multiplicity at least $m$ in $T$. In other words, every string in $\rho_I(S)$ has to appear at least $m$ times in $\rho_I(S)$. Here $m$ is some threshold fixed in advance, e.g., $m=100$.

Suppose we partition the set $\{1,2,\dots,n\}$ into three disjoint sets: $I_1 \cup I_2 \cup I_3 = \{1,2,\dots,n\}$, where $I_1,I_2,I_3$ are mutually disjoint. We'll say that this partition is good if $I_1$ is good, $I_2$ is good, and $I_3$ is good (in other words, projecting onto each index set yields a multiset where all elements have multiplicity at least $m$).

I want to find an algorithm to compute whether there exists any good partition (and if yes, to output an example of a good partition), given $S$ and $m$. Can anyone suggest a good algorithm for this? Or, if this is intractable, I would be satisfied with good heuristics or approximation algorithms. Or, is it easier if I want to partition $\{1,\dots,n\}$ into two sets $I_1,I_2$? Does anyone know of any algorithmic techniques that might be relevant, or any connection to problems that have been studied in the literature?

This arises from a practical application I have, where (intuitively) the requirement that all multiplicities of the reduced set be at least $m$ corresponds to a sort of privacy/anonymity/plausible deniability property, and larger values of $m$ correspond to greater anonymity. Sample parameters for my problem might be something like: $S$ is a multiset with thousands or tens of thousands of strings (counting multiplicity) and hundreds or thousands of unique strings (not counting multiplicity); $m$ is maybe 100 or so; $n$ is maybe 20-200 or so. References to research papers would be fine. I hope this kind of question is suitable for this site; if not, let me know and I'd be happy to flag it to have it migrated over to CS.StackExchange.

$\endgroup$
  • $\begingroup$ as an aside, this looks very much like $k$-anonymity, which incidentally is a horrible way to achieve privacy or anonymity because it's very vulnerable to simple linkage attacks, see for example arxiv.org/pdf/0803.0032v2.pdf $\endgroup$ – Sasho Nikolov May 10 '13 at 4:20
  • $\begingroup$ Thanks, @SashoNikolov. As it happens, I know about those problems and they aren't an issue for my application (for reasons that are beyond the scope of this question), but you are absolutely right to raise this warning -- I appreciate the note of caution! $\endgroup$ – D.W. May 10 '13 at 4:29

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.