  In the Pattern Masking for Dictionary Matching (PMDM) problem, we are given a
dictionary $\mathcal{D}$ of $d$ strings, each of length $\ell$, a query string
$q$ of length $\ell$, and a positive integer $z$, and we are asked to compute a
smallest set $K\subseteq\{1,\ldots,\ell\}$, so that if $q[i]$, for all $i\in
K$, is replaced by a wildcard, then $q$ matches at least $z$ strings from
$\mathcal{D}$. The PMDM problem lies at the heart of two important applications
featured in large-scale real-world systems: record linkage of databases that
contain sensitive information, and query term dropping. In both applications,
solving PMDM allows for providing data utility guarantees as opposed to
existing approaches.
  We first show, through a reduction from the well-known $k$-Clique problem,
that a decision version of the PMDM problem is NP-complete, even for strings
over a binary alphabet. We present a data structure for PMDM that answers
queries over $\mathcal{D}$ in time
$\mathcal{O}(2^{\ell/2}(2^{\ell/2}+\tau)\ell)$ and requires space
$\mathcal{O}(2^{\ell}d^2/\tau^2+2^{\ell/2}d)$, for any parameter
$\tau\in[1,d]$. We also approach the problem from a more practical perspective.
We show an $\mathcal{O}((d\ell)^{k/3}+d\ell)$-time and
$\mathcal{O}(d\ell)$-space algorithm for PMDM if $k=|K|=\mathcal{O}(1)$. We
generalize our exact algorithm to mask multiple query strings simultaneously.
We complement our results by showing a two-way polynomial-time reduction
between PMDM and the Minimum Union problem [Chlamt\'{a}\v{c} et al., SODA
2017]. This gives a polynomial-time
$\mathcal{O}(d^{1/4+\epsilon})$-approximation algorithm for PMDM, which is
tight under plausible complexity conjectures.

Data Structures and Algorithms