Pattern Masking for Dictionary Matching

Data masking is a common technique for sanitizing sensitive data maintained in database systems, and it is also becoming increasingly important in various application areas, such as in record linkage of personal data. This work formalizes the Pattern Masking for Dictionary Matching (PPSM) problem. In PPSM, we are given a dictionary $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 $Ksubseteq{1,ldots,ell}$, so that if $q[i]$ is replaced by a wildcard for all $iin K$, then $q$ matches at least $z$ strings from $D$. Solving {PPSM} allows 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 PPSM problem is NP-complete, even for strings over a binary alphabet. We thus approach the problem from a more practical perspective. We show a combinatorial $cO((dell)^{|K|/3}+dell)$-time and $cO(dell)$-space algorithm for PPSM for $|K|=cO(1)$. In fact, we show that we cannot hope for a faster combinatorial algorithm, unless the combinatorial $k$-Clique hypothesis fails [Abboud et al., SIAM J.~Comput.~2018; Lincoln et al., SODA 2018]. We also generalize this algorithm for the problem of masking multiple query strings simultaneously so that every string has at least $z$ matches in $D$. Note that PPSM can be viewed as a generalization of the decision version of the dictionary matching with mismatches problem: by querying a PPSM data structure with string $q$ and $z=1$, one obtains the minimal number of mismatches of $q$ with any string from $D$. The query time or space of all known data structures for the emph{more restricted} problem of dictionary matching with at most $k$ mismatches incurs some exponential factor with respect to $k$. %In fact, for reporting, this barrier cannot be broken (for some $k$) in the pointer machine model of computation [Cohen-Addad et al., SODA 2019]. A simple exact algorithm for PPSM runs in time $cO(2^ell d)$. We present a data structure for PPSM that answers queries over $D$ in time $cO(2^{ell/2}(2^{ell/2}+ au)ell)$ and requires space $cO(2^{ell}d^2/ au^2+2^{ell/2}d)$, for any parameter $ auin[1,d]$. We complement our results by showing a two-way polynomial-time reduction between PPSM and the Minimum Union problem [Chlamt'{a}{c} et al., SODA 2017]. This gives a polynomial-time $cO(d^{1/4+epsilon})$-approximation algorithm for PPSM, which is tight under a plausible complexity conjecture.