String sanitization under edit distance: Improved and generalized

Takuya Mieno*, Solon P. Pissis, Leen Stougie, Michelle Sweering

*Corresponding author for this work

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

Abstract

Let W be a string of length n over an alphabet S, k be a positive integer, and S be a set of length-k substrings of W. The ETFS problem (Edit distance, Total order, Frequency, Sanitization) asks us to construct a string XEDsuch that: (i) no string of S occurs in XED; (ii) the order of all other length-k substrings over Σ (and thus the frequency) is the same in W and in XED; and (iii) XEDhas minimal edit distance to W. When W represents an individual's data and S represents a set of confidential patterns, the ETFS problem asks for transforming W to preserve its privacy and its utility [Bernardini et al., ECML PKDD 2019]. ETFS can be solved in O(n2k) time [Bernardini et al., CPM 2020]. The same paper shows that ETFS cannot be solved in O(n2-δ) time, for any δ > 0, unless the Strong Exponential Time Hypothesis (SETH) is false. Our main results can be summarized as follows: An O(n2log2k)-time algorithm to solve ETFS. An O(n2log2n)-time algorithm to solve AETFS (Arbitrary lengths, Edit distance, Total order, Frequency, Sanitization), a generalization of ETFS in which the elements of S can have arbitrary lengths. Our algorithms are thus optimal up to subpolynomial factors, unless SETH fails. In order to arrive at these results, we develop new techniques for computing a variant of the standard dynamic programming (DP) table for edit distance. In particular, we simulate the DP table computation using a directed acyclic graph in which every node is assigned to a smaller DP table. We then focus on redundancy in these DP tables and exploit a tabulation technique according to dyadic intervals to obtain an optimal alignment in O(n2) total time1. Beyond string sanitization, our techniques may inspire solutions to other problems related to regular expressions or context-free grammars.

Original languageEnglish
Title of host publication32nd Annual Symposium on Combinatorial Pattern Matching, CPM 2021
EditorsPawel Gawrychowski, Tatiana Starikovskaya
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771863
DOIs
Publication statusPublished - 1 Jul 2021
Event32nd Annual Symposium on Combinatorial Pattern Matching, CPM 2021 - Wroclaw, Poland
Duration: 5 Jul 20217 Jul 2021

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume191
ISSN (Print)1868-8969

Conference

Conference32nd Annual Symposium on Combinatorial Pattern Matching, CPM 2021
Country/TerritoryPoland
CityWroclaw
Period5/07/217/07/21

Bibliographical note

Funding Information:
Funding Takuya Mieno: JSPS KAKENHI Grant Number JP20J11983 Leen Stougie: Netherlands Organisation for Scientific Research (NWO) through Gravitation-grant NETWORKS-024.002.003 Michelle Sweering: Netherlands Organisation for Scientific Research (NWO) through Gravitation-grant NETWORKS-024.002.003

Publisher Copyright:
© 2021 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.

Copyright:
Copyright 2021 Elsevier B.V., All rights reserved.

Keywords

  • Data sanitization
  • Dynamic programming
  • Edit distance
  • String algorithms

Fingerprint

Dive into the research topics of 'String sanitization under edit distance: Improved and generalized'. Together they form a unique fingerprint.

Cite this