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

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-review

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
Place of Publication	Dagstuhl
Publisher	Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages	1-14
Number of pages	14
ISBN (Electronic)	9783959771498
DOIs	https://doi.org/10.4230/LIPIcs.CPM.2020.7
Publication status	Published - 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.

Funding

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.

Funders	Funder number
Marie Skłodowska-Curie
China Scholarship Council
Horizon 2020 Framework Programme	872539
Nederlandse Organisatie voor Wetenschappelijk Onderzoek	024.002.003, NETWORKS-024.002.003

Keywords

Conditional lower bound
Data sanitization
Dynamic programming
Edit distance
String algorithms

Access to Document

10.4230/LIPIcs.CPM.2020.7

Persistent URL (handle)

Persistent link

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) (pp. 1-14). Article 7 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 161). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.CPM.2020.7

Bernardini, Giulia ; Chen, Huiping ; Loukides, Grigorios et al. / String Sanitization under Edit Distance. 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020). editor / Inge Li Gortz ; Oren Weimann. Dagstuhl : Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2020. pp. 1-14 (Leibniz International Proceedings in Informatics, LIPIcs).

@inproceedings{add9115e93f7404b89c2d369b580f3f9,

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",

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

language = "English",

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

publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

pages = "1--14",

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

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

}

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- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Dagstuhl, pp. 1-14, 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. Dagstuhl: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2020. p. 1-14 7 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 161).

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-review

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

Y1 - 2020

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 - https://www.scopus.com/pages/publications/85088401873

UR - https://www.scopus.com/pages/publications/85088401873#tab=citedBy

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

SP - 1

EP - 14

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

A2 - Gortz, Inge Li

A2 - Weimann, Oren

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

CY - Dagstuhl

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

Y2 - 17 June 2020 through 19 June 2020

ER -

Bernardini G, Chen H, Loukides G, Pisanti N, Pissis SP , Stougie L et al. String Sanitization under Edit Distance. In Gortz IL, Weimann O, editors, 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020). Dagstuhl: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2020. p. 1-14. 7. (Leibniz International Proceedings in Informatics, LIPIcs). Epub 2020 Jun 9. doi: 10.4230/LIPIcs.CPM.2020.7

String Sanitization under Edit Distance

Abstract

Publication series

Conference

Bibliographical note

Funding

Keywords

Access to Document

Persistent URL (handle)

Other files and links

Fingerprint

Cite this