</> Code with Papers by Syntology

Papers β€Ί Pattern Masking for Dictionary Matching

Pattern Masking for Dictionary Matching

29 Jun 2020arXiv:2006.16137links table onlyarchive 2025-07-28

Panagiotis Charalampopoulos, Huiping Chen, Peter Christen, Grigorios Loukides, Nadia Pisanti, Solon P. Pissis, Jakub Radoszewski

The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.

In the Pattern Masking for Dictionary Matching (PMDM) problem, we are given a dictionary π’Ÿ of d strings, each of length β„“, a query string q of length β„“, and a positive integer z, and we are asked to compute a smallest set KβŠ†{1,…,β„“}, so that if q[i], for all i∈K, is replaced by a wildcard, then q matches at least z strings from π’Ÿ. 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 π’Ÿ in time π’ͺ(2^(β„“/2)(2^(β„“/2)+Ο„)β„“) and requires space π’ͺ(2^β„“dΒ²/τ²+2^(β„“/2)d), for any parameter Ο„βˆˆ[1,d]. We also approach the problem from a more practical perspective. We show an π’ͺ((dβ„“)^(k/3)+dβ„“)-time and π’ͺ(dβ„“)-space algorithm for PMDM if k=|K|=π’ͺ(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 π’ͺ(d^(1/4+Ο΅))-approximation algorithm for PMDM, which is tight under plausible complexity conjectures.

PaperPDFCode

Code

bitbucket.org/pattern-masking/pmdm officialmentioned in paper report

Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.

Code Syntology ran Syntology

Not run by Syntology. Nothing on this page verifies that the listed code works.

Results from the paper archive 2025-07-28

No leaderboard rows for this paper in the archive.

Report a problem or propose a change Β· a person checks every report against the paper or source before anything changes; decisions are listed on /corrections