String Sanitization under Edit Distance

Giulia Bernardini; Huiping Chen; Grigorios Loukides; Nadia Pisanti; Solon P. Pissis; Leen Stougie; Michelle Sweering

doi:10.4230/LIPIcs.CPM.2020.7

String Sanitization under Edit Distance

Giulia Bernardini, Huiping Chen, Grigorios Loukides, Nadia Pisanti, Solon P. Pissis, Leen Stougie, Michelle Sweering

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

9 Citations (Scopus)

Abstract

Let W be a string of length n over an alphabet, k be a positive integer, and S be a set of length-k substrings of W. The ETFS problem asks us to construct a string XED such that: (i) no string of S occurs in XED; (ii) the order of all other length-k substrings overis the same in W and in XED; and (iii) XED has minimal edit distance to W. When W represents an individual's data and S 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 O(kn2) 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 O(n2-) 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. 2012 ACM Subject Classification Theory of computation ! Pattern matching.

Original language	English
Title of host publication	31st Annual Symposium on Combinatorial Pattern Matching, CPM 2020
Editors	Inge Li Gortz, Oren Weimann
Publisher	Schloss Dagstuhl
ISBN (Electronic)	9783959771498
DOIs	https://doi.org/10.4230/LIPIcs.CPM.2020.7
Publication status	Published - 1 Jun 2020
Event	31st Annual Symposium on Combinatorial Pattern Matching, CPM 2020 - Copenhagen, Denmark Duration: 17 Jun 2020 → 19 Jun 2020

Publication series

Name	Leibniz International Proceedings in Informatics, LIPIcs
Volume	161
ISSN (Print)	1868-8969

Conference

Conference	31st Annual Symposium on Combinatorial Pattern Matching, CPM 2020
Country/Territory	Denmark
City	Copenhagen
Period	17/06/20 → 19/06/20

Bibliographical note

Funding Information:
Funding This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 872539. Giulia Bernardini: Partially supported by a research internship at CWI. Huiping Chen: Supported by a Ph.D scholarship from China Scholarship Council. Leen Stougie: Supported by the Netherlands Organisation for Scientific Research (NWO) through Gravitation-grant NETWORKS-024.002.003. Michelle Sweering: Supported by the Netherlands Organisation for Scientific Research (NWO) through Gravitation-grant NETWORKS-024.002.003.

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

Keywords

Conditional lower bound
Data sanitization
Dynamic programming
Edit distance
String algorithms

ASJC Scopus subject areas

Software

Access to Document

10.4230/LIPIcs.CPM.2020.7

Cite this

Bernardini, G., Chen, H., Loukides, G., Pisanti, N., Pissis, S. P., Stougie, L., & Sweering, M. (2020). String Sanitization under Edit Distance. In I. L. Gortz, & O. Weimann (Eds.), 31st Annual Symposium on Combinatorial Pattern Matching, CPM 2020 Article 7 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 161). Schloss Dagstuhl. https://doi.org/10.4230/LIPIcs.CPM.2020.7

@inproceedings{6b7fd0ca6beb4e68b38dbd2c7a6c9648,

title = "String Sanitization under Edit Distance",

abstract = "Let W be a string of length n over an alphabet, k be a positive integer, and S be a set of length-k substrings of W. The ETFS problem asks us to construct a string XED such that: (i) no string of S occurs in XED; (ii) the order of all other length-k substrings overis the same in W and in XED; and (iii) XED has minimal edit distance to W. When W represents an individual's data and S 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 O(kn2) 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 O(n2-) 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{\"u}nnemann, FOCS 2015], to ETFS. 2012 ACM Subject Classification Theory of computation ! Pattern matching.",

keywords = "Conditional lower bound, Data sanitization, Dynamic programming, Edit distance, String algorithms",

author = "Giulia Bernardini and Huiping Chen and Grigorios Loukides and Nadia Pisanti and Pissis, {Solon P.} and Leen Stougie and Michelle Sweering",

note = "Funding Information: Funding This project has received funding from the European Union{\textquoteright}s Horizon 2020 research and innovation programme under the Marie Sk{\l}odowska-Curie grant agreement No 872539. Giulia Bernardini: Partially supported by a research internship at CWI. Huiping Chen: Supported by a Ph.D scholarship from China Scholarship Council. Leen Stougie: Supported by the Netherlands Organisation for Scientific Research (NWO) through Gravitation-grant NETWORKS-024.002.003. Michelle Sweering: Supported by the Netherlands Organisation for Scientific Research (NWO) through Gravitation-grant NETWORKS-024.002.003. Publisher Copyright: {\textcopyright} 2020 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.; 31st Annual Symposium on Combinatorial Pattern Matching, CPM 2020 ; Conference date: 17-06-2020 Through 19-06-2020",

year = "2020",

month = jun,

day = "1",

doi = "10.4230/LIPIcs.CPM.2020.7",

language = "English",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl",

editor = "Gortz, {Inge Li} and Oren Weimann",

booktitle = "31st Annual Symposium on Combinatorial Pattern Matching, CPM 2020",

address = "Germany",

}

Bernardini, G, Chen, H, Loukides, G, Pisanti, N, Pissis, SP, Stougie, L & Sweering, M 2020, String Sanitization under Edit Distance. in IL Gortz & O Weimann (eds), 31st Annual Symposium on Combinatorial Pattern Matching, CPM 2020., 7, Leibniz International Proceedings in Informatics, LIPIcs, vol. 161, Schloss Dagstuhl, 31st Annual Symposium on Combinatorial Pattern Matching, CPM 2020, Copenhagen, Denmark, 17/06/20. https://doi.org/10.4230/LIPIcs.CPM.2020.7

String Sanitization under Edit Distance. / Bernardini, Giulia; Chen, Huiping; Loukides, Grigorios et al.
31st Annual Symposium on Combinatorial Pattern Matching, CPM 2020. ed. / Inge Li Gortz; Oren Weimann. Schloss Dagstuhl, 2020. 7 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 161).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - String Sanitization under Edit Distance

AU - Bernardini, Giulia

AU - Chen, Huiping

AU - Loukides, Grigorios

AU - Pisanti, Nadia

AU - Pissis, Solon P.

AU - Stougie, Leen

AU - Sweering, Michelle

N1 - Funding Information: Funding This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 872539. Giulia Bernardini: Partially supported by a research internship at CWI. Huiping Chen: Supported by a Ph.D scholarship from China Scholarship Council. Leen Stougie: Supported by the Netherlands Organisation for Scientific Research (NWO) through Gravitation-grant NETWORKS-024.002.003. Michelle Sweering: Supported by the Netherlands Organisation for Scientific Research (NWO) through Gravitation-grant NETWORKS-024.002.003. Publisher Copyright: © 2020 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.

PY - 2020/6/1

Y1 - 2020/6/1

N2 - Let W be a string of length n over an alphabet, k be a positive integer, and S be a set of length-k substrings of W. The ETFS problem asks us to construct a string XED such that: (i) no string of S occurs in XED; (ii) the order of all other length-k substrings overis the same in W and in XED; and (iii) XED has minimal edit distance to W. When W represents an individual's data and S 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 O(kn2) 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 O(n2-) 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. 2012 ACM Subject Classification Theory of computation ! Pattern matching.

AB - Let W be a string of length n over an alphabet, k be a positive integer, and S be a set of length-k substrings of W. The ETFS problem asks us to construct a string XED such that: (i) no string of S occurs in XED; (ii) the order of all other length-k substrings overis the same in W and in XED; and (iii) XED has minimal edit distance to W. When W represents an individual's data and S 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 O(kn2) 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 O(n2-) 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. 2012 ACM Subject Classification Theory of computation ! Pattern matching.

KW - Conditional lower bound

KW - Data sanitization

KW - Dynamic programming

KW - Edit distance

KW - String algorithms

UR - http://www.scopus.com/inward/record.url?scp=85088401873&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.CPM.2020.7

DO - 10.4230/LIPIcs.CPM.2020.7

M3 - Conference contribution

AN - SCOPUS:85088401873

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 31st Annual Symposium on Combinatorial Pattern Matching, CPM 2020

A2 - Gortz, Inge Li

A2 - Weimann, Oren

PB - Schloss Dagstuhl

T2 - 31st Annual Symposium on Combinatorial Pattern Matching, CPM 2020

Y2 - 17 June 2020 through 19 June 2020

ER -

String Sanitization under Edit Distance

Abstract

Publication series

Conference

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this