2026-07-23T19:07:49Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12132 2024-03-06T10:49:22Z ddc:004 open_access

String Sanitization Under Edit Distance Bernardini, Giulia Chen, Huiping Loukides, Grigorios Pisanti, Nadia Pissis, Solon P. Stougie, Leen Sweering, Michelle String algorithms data sanitization edit distance dynamic programming conditional lower bound Let W be a string of length n over an alphabet Σ, k be a positive integer, and 𝒮 be a set of length-k substrings of W. The ETFS problem asks us to construct a string X_{ED} such that: (i) no string of 𝒮 occurs in X_{ED}; (ii) the order of all other length-k substrings over Σ is the same in W and in X_{ED}; and (iii) X_{ED} has minimal edit distance to W. When W represents an individual’s data and 𝒮 represents a set of confidential substrings, algorithms solving ETFS can be applied for utility-preserving string sanitization [Bernardini et al., ECML PKDD 2019]. Our first result here is an algorithm to solve ETFS in 𝒪(kn²) time, which improves on the state of the art [Bernardini et al., arXiv 2019] by a factor of |Σ|. Our algorithm is based on a non-trivial modification of the classic dynamic programming algorithm for computing the edit distance between two strings. Notably, we also show that ETFS cannot be solved in 𝒪(n^{2-δ}) time, for any δ>0, unless the strong exponential time hypothesis is false. To achieve this, we reduce the edit distance problem, which is known to admit the same conditional lower bound [Bringmann and Künnemann, FOCS 2015], to ETFS. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Giulia Bernardini and Huiping Chen and Grigorios Loukides and Nadia Pisanti and Solon P. Pissis and Leen Stougie and Michelle Sweering 2020 Is Part Of LIPIcs, Volume 161, 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2020.7 urn:nbn:de:0030-drops-121324 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2020.7 eng https://creativecommons.org/licenses/by/3.0/legalcode