121.
Charalampopoulos, Panagiotis; Chen, Huiping; Christen, Peter; Loukides, Grigorios; Pisanti, Nadia; Pissis, Solon P.; Radoszewski, Jakub
Pattern Masking for Dictionary Matching Proceedings Article
In: Ahn, Hee-Kap; Sadakane, Kunihiko (Ed.): 32nd International Symposium on Algorithms and Computation (ISAAC 2021), pp. 65:1β65:19, Schloss Dagstuhl -- Leibniz-Zentrum fΓΌr Informatik, Dagstuhl, Germany, 2021, ISSN: 1868-8969.
Abstract | Links | BibTeX | Tags: WP1: Primary CPG
@inproceedings{Charalampopoulos2021,
title = {Pattern Masking for Dictionary Matching},
author = {Panagiotis Charalampopoulos and Huiping Chen and Peter Christen and Grigorios Loukides and Nadia Pisanti and Solon P. Pissis and Jakub Radoszewski},
editor = {Hee-Kap Ahn and Kunihiko Sadakane},
doi = {10.4230/LIPIcs.ISAAC.2021.65},
issn = {1868-8969},
year = {2021},
date = {2021-01-01},
urldate = {2021-01-01},
booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
volume = {212},
pages = {65:1--65:19},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum fΓΌr Informatik},
address = {Dagstuhl, Germany},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
abstract = {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 (PMDM) problem. In PMDM, 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] is replaced by a wildcard for all i β K, then q matches at least z strings from π. Solving PMDM 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 PMDM 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 πͺ((dπ)^{|K|/3}+dπ)-time and πͺ(dπ)-space algorithm for PMDM for |K| = πͺ(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 π.
Note that PMDM can be viewed as a generalization of the decision version of the dictionary matching with mismatches problem: by querying a PMDM data structure with string q and z = 1, one obtains the minimal number of mismatches of q with any string from π. The query time or space of all known data structures for the more restricted problem of dictionary matching with at most k mismatches incurs some exponential factor with respect to k. A simple exact algorithm for PMDM runs in time πͺ(2^π d). 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 complement our results by showing a two-way polynomial-time reduction between PMDM and the Minimum Union problem [ChlamtΓ‘Δ et al., SODA 2017]. This gives a polynomial-time πͺ(d^{1/4+Ξ΅})-approximation algorithm for PMDM, which is tight under a plausible complexity conjecture. },
keywords = {WP1: Primary CPG},
pubstate = {published},
tppubtype = {inproceedings}
}
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 (PMDM) problem. In PMDM, 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] is replaced by a wildcard for all i β K, then q matches at least z strings from π. Solving PMDM 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 PMDM 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 πͺ((dπ)^{|K|/3}+dπ)-time and πͺ(dπ)-space algorithm for PMDM for |K| = πͺ(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 π.
Note that PMDM can be viewed as a generalization of the decision version of the dictionary matching with mismatches problem: by querying a PMDM data structure with string q and z = 1, one obtains the minimal number of mismatches of q with any string from π. The query time or space of all known data structures for the more restricted problem of dictionary matching with at most k mismatches incurs some exponential factor with respect to k. A simple exact algorithm for PMDM runs in time πͺ(2^π d). 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 complement our results by showing a two-way polynomial-time reduction between PMDM and the Minimum Union problem [ChlamtΓ‘Δ et al., SODA 2017]. This gives a polynomial-time πͺ(d^{1/4+Ξ΅})-approximation algorithm for PMDM, which is tight under a plausible complexity conjecture.
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 thus approach the problem from a more practical perspective. We show a combinatorial πͺ((dπ)^{|K|/3}+dπ)-time and πͺ(dπ)-space algorithm for PMDM for |K| = πͺ(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 π.
Note that PMDM can be viewed as a generalization of the decision version of the dictionary matching with mismatches problem: by querying a PMDM data structure with string q and z = 1, one obtains the minimal number of mismatches of q with any string from π. The query time or space of all known data structures for the more restricted problem of dictionary matching with at most k mismatches incurs some exponential factor with respect to k. A simple exact algorithm for PMDM runs in time πͺ(2^π d). 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 complement our results by showing a two-way polynomial-time reduction between PMDM and the Minimum Union problem [ChlamtΓ‘Δ et al., SODA 2017]. This gives a polynomial-time πͺ(d^{1/4+Ξ΅})-approximation algorithm for PMDM, which is tight under a plausible complexity conjecture.
122.
Cazaux, Bastien; Rivals, Eric
Greedy-reduction from Shortest Linear Superstring to Shortest Circular Superstring Unpublished
arXiv, 2020.
Abstract | Links | BibTeX | Tags: WP1: Primary CPG
@unpublished{Cazaux2020,
title = {Greedy-reduction from Shortest Linear Superstring to Shortest Circular Superstring},
author = {Bastien Cazaux and Eric Rivals},
doi = {10.48550/ARXIV.2012.08878},
year = {2020},
date = {2020-01-01},
urldate = {2020-01-01},
publisher = {arXiv},
abstract = {A superstring of a set of strings correspond to a string which contains all the other strings as substrings. The problem of finding the Shortest Linear Superstring is a well-know and well-studied problem in stringology. We present here a variant of this problem, the Shortest Circular Superstring problem where the sought superstring is a circular string. We show a strong link between these two problems and prove that the Shortest Circular Superstring problem is NP-complete. Moreover, we propose a new conjecture on the approximation ratio of the Shortest Circular Superstring problem. },
howpublished = {arXiv},
keywords = {WP1: Primary CPG},
pubstate = {published},
tppubtype = {unpublished}
}
A superstring of a set of strings correspond to a string which contains all the other strings as substrings. The problem of finding the Shortest Linear Superstring is a well-know and well-studied problem in stringology. We present here a variant of this problem, the Shortest Circular Superstring problem where the sought superstring is a circular string. We show a strong link between these two problems and prove that the Shortest Circular Superstring problem is NP-complete. Moreover, we propose a new conjecture on the approximation ratio of the Shortest Circular Superstring problem.