Hide and mine in strings: Hardness and algorithms

Giulia Bernardini; Alessio Conte; Garance Gourdel; Roberto Grossi; Grigorios Loukides; Nadia Pisanti; Solon P. Pissis; Giulia Punzi; Leen Stougie; Michelle Sweering

doi:10.1109/ICDM50108.2020.00103

Hide and mine in strings: Hardness and algorithms

Giulia Bernardini
, Alessio Conte
, Garance Gourdel
, Roberto Grossi
, Grigorios Loukides
, Nadia Pisanti
, Solon P. Pissis
, Giulia Punzi
, Leen Stougie
, Michelle Sweering

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

Abstract

We initiate a study on the fundamental relation between data sanitization (i.e., the process of hiding confidential information in a given dataset) and frequent pattern mining, in the context of sequential (string) data. Current methods for string sanitization hide confidential patterns introducing, however, a number of spurious patterns that may harm the utility of frequent pattern mining. The main computational problem is to minimize this harm. Our contribution here is twofold. First, we present several hardness results, for different variants of this problem, essentially showing that these variants cannot be solved or even be approximated in polynomial time. Second, we propose integer linear programming formulations for these variants and algorithms to solve them, which work in polynomial time under certain realistic assumptions on the problem parameters.

Original language	English
Title of host publication	2020 [20th] IEEE International Conference on Data Mining (ICDM)
Subtitle of host publication	[Proceedings]
Editors	Claudia Plant, Haixun Wang, Alfredo Cuzzocrea, Carlo Zaniolo, Xindong Wu
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	924-929
Number of pages	6
ISBN (Electronic)	9781728183169
DOIs	https://doi.org/10.1109/ICDM50108.2020.00103
Publication status	Published - 9 Feb 2021
Event	20th IEEE International Conference on Data Mining, ICDM 2020 - Virtual, Sorrento, Italy Duration: 17 Nov 2020 → 20 Nov 2020

Publication series

Name	Proceedings - IEEE International Conference on Data Mining, ICDM
Volume	2020-November
ISSN (Print)	1550-4786

Conference

Conference	20th IEEE International Conference on Data Mining, ICDM 2020
Country/Territory	Italy
City	Virtual, Sorrento
Period	17/11/20 → 20/11/20

Bibliographical note

Funding Information:
Acknowledgments. MIUR Grant 20174LF3T8 AHeAD; University of Pisa ”PRA – Progetti di Ricerca di Ateneo” (Institutional Research Grants) Grant PRA 20202021 26 “Metodi Informatici Integrati per la Biomedica”; and NWO Gravitation-grant NETWORKS-024.002.003.

Publisher Copyright:
© 2020 IEEE.

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

Funding

Acknowledgments. MIUR Grant 20174LF3T8 AHeAD; University of Pisa ”PRA – Progetti di Ricerca di Ateneo” (Institutional Research Grants) Grant PRA 20202021 26 “Metodi Informatici Integrati per la Biomedica”; and NWO Gravitation-grant NETWORKS-024.002.003.

Funders	Funder number
Nederlandse Organisatie voor Wetenschappelijk Onderzoek	024.002.003, NETWORKS-024.002.003
Università di Pisa	PRA 20202021 26
Ministero dell’Istruzione, dell’Università e della Ricerca	20174LF3T8 AHeAD

Keywords

Data privacy
Data sanitization
Frequent pattern mining
Knowledge hiding
String algorithms

Access to Document

10.1109/ICDM50108.2020.00103

Persistent URL (handle)

Persistent link

Cite this

Bernardini, G., Conte, A., Gourdel, G., Grossi, R., Loukides, G., Pisanti, N., Pissis, S. P., Punzi, G., Stougie, L., & Sweering, M. (2021). Hide and mine in strings: Hardness and algorithms. In C. Plant, H. Wang, A. Cuzzocrea, C. Zaniolo, & X. Wu (Eds.), 2020 [20th] IEEE International Conference on Data Mining (ICDM): [Proceedings] (pp. 924-929). Article 9338348 (Proceedings - IEEE International Conference on Data Mining, ICDM; Vol. 2020-November). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ICDM50108.2020.00103

Bernardini, Giulia ; Conte, Alessio ; Gourdel, Garance et al. / Hide and mine in strings : Hardness and algorithms. 2020 [20th] IEEE International Conference on Data Mining (ICDM): [Proceedings]. editor / Claudia Plant ; Haixun Wang ; Alfredo Cuzzocrea ; Carlo Zaniolo ; Xindong Wu. Institute of Electrical and Electronics Engineers Inc., 2021. pp. 924-929 (Proceedings - IEEE International Conference on Data Mining, ICDM).

@inproceedings{507a3357d5e947bcba0c42f2185a1620,

title = "Hide and mine in strings: Hardness and algorithms",

abstract = "We initiate a study on the fundamental relation between data sanitization (i.e., the process of hiding confidential information in a given dataset) and frequent pattern mining, in the context of sequential (string) data. Current methods for string sanitization hide confidential patterns introducing, however, a number of spurious patterns that may harm the utility of frequent pattern mining. The main computational problem is to minimize this harm. Our contribution here is twofold. First, we present several hardness results, for different variants of this problem, essentially showing that these variants cannot be solved or even be approximated in polynomial time. Second, we propose integer linear programming formulations for these variants and algorithms to solve them, which work in polynomial time under certain realistic assumptions on the problem parameters.",

keywords = "Data privacy, Data sanitization, Frequent pattern mining, Knowledge hiding, String algorithms",

author = "Giulia Bernardini and Alessio Conte and Garance Gourdel and Roberto Grossi and Grigorios Loukides and Nadia Pisanti and Pissis, \{Solon P.\} and Giulia Punzi and Leen Stougie and Michelle Sweering",

note = "Funding Information: Acknowledgments. MIUR Grant 20174LF3T8 AHeAD; University of Pisa ”PRA – Progetti di Ricerca di Ateneo” (Institutional Research Grants) Grant PRA 20202021 26 “Metodi Informatici Integrati per la Biomedica”; and NWO Gravitation-grant NETWORKS-024.002.003. Publisher Copyright: {\textcopyright} 2020 IEEE. Copyright: Copyright 2021 Elsevier B.V., All rights reserved.; 20th IEEE International Conference on Data Mining, ICDM 2020 ; Conference date: 17-11-2020 Through 20-11-2020",

year = "2021",

month = feb,

day = "9",

doi = "10.1109/ICDM50108.2020.00103",

language = "English",

series = "Proceedings - IEEE International Conference on Data Mining, ICDM",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "924--929",

editor = "Claudia Plant and Haixun Wang and Alfredo Cuzzocrea and Carlo Zaniolo and Xindong Wu",

booktitle = "2020 [20th] IEEE International Conference on Data Mining (ICDM)",

address = "United States",

}

Bernardini, G, Conte, A, Gourdel, G, Grossi, R, Loukides, G, Pisanti, N, Pissis, SP, Punzi, G, Stougie, L & Sweering, M 2021, Hide and mine in strings: Hardness and algorithms. in C Plant, H Wang, A Cuzzocrea, C Zaniolo & X Wu (eds), 2020 [20th] IEEE International Conference on Data Mining (ICDM): [Proceedings]., 9338348, Proceedings - IEEE International Conference on Data Mining, ICDM, vol. 2020-November, Institute of Electrical and Electronics Engineers Inc., pp. 924-929, 20th IEEE International Conference on Data Mining, ICDM 2020, Virtual, Sorrento, Italy, 17/11/20. https://doi.org/10.1109/ICDM50108.2020.00103

Hide and mine in strings: Hardness and algorithms. / Bernardini, Giulia; Conte, Alessio; Gourdel, Garance et al.
2020 [20th] IEEE International Conference on Data Mining (ICDM): [Proceedings]. ed. / Claudia Plant; Haixun Wang; Alfredo Cuzzocrea; Carlo Zaniolo; Xindong Wu. Institute of Electrical and Electronics Engineers Inc., 2021. p. 924-929 9338348 (Proceedings - IEEE International Conference on Data Mining, ICDM; Vol. 2020-November).

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

TY - GEN

T1 - Hide and mine in strings

T2 - 20th IEEE International Conference on Data Mining, ICDM 2020

AU - Bernardini, Giulia

AU - Conte, Alessio

AU - Gourdel, Garance

AU - Grossi, Roberto

AU - Loukides, Grigorios

AU - Pisanti, Nadia

AU - Pissis, Solon P.

AU - Punzi, Giulia

AU - Stougie, Leen

AU - Sweering, Michelle

N1 - Funding Information: Acknowledgments. MIUR Grant 20174LF3T8 AHeAD; University of Pisa ”PRA – Progetti di Ricerca di Ateneo” (Institutional Research Grants) Grant PRA 20202021 26 “Metodi Informatici Integrati per la Biomedica”; and NWO Gravitation-grant NETWORKS-024.002.003. Publisher Copyright: © 2020 IEEE. Copyright: Copyright 2021 Elsevier B.V., All rights reserved.

PY - 2021/2/9

Y1 - 2021/2/9

N2 - We initiate a study on the fundamental relation between data sanitization (i.e., the process of hiding confidential information in a given dataset) and frequent pattern mining, in the context of sequential (string) data. Current methods for string sanitization hide confidential patterns introducing, however, a number of spurious patterns that may harm the utility of frequent pattern mining. The main computational problem is to minimize this harm. Our contribution here is twofold. First, we present several hardness results, for different variants of this problem, essentially showing that these variants cannot be solved or even be approximated in polynomial time. Second, we propose integer linear programming formulations for these variants and algorithms to solve them, which work in polynomial time under certain realistic assumptions on the problem parameters.

AB - We initiate a study on the fundamental relation between data sanitization (i.e., the process of hiding confidential information in a given dataset) and frequent pattern mining, in the context of sequential (string) data. Current methods for string sanitization hide confidential patterns introducing, however, a number of spurious patterns that may harm the utility of frequent pattern mining. The main computational problem is to minimize this harm. Our contribution here is twofold. First, we present several hardness results, for different variants of this problem, essentially showing that these variants cannot be solved or even be approximated in polynomial time. Second, we propose integer linear programming formulations for these variants and algorithms to solve them, which work in polynomial time under certain realistic assumptions on the problem parameters.

KW - Data privacy

KW - Data sanitization

KW - Frequent pattern mining

KW - Knowledge hiding

KW - String algorithms

UR - https://www.scopus.com/pages/publications/85100906384

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

U2 - 10.1109/ICDM50108.2020.00103

DO - 10.1109/ICDM50108.2020.00103

M3 - Conference contribution

AN - SCOPUS:85100906384

T3 - Proceedings - IEEE International Conference on Data Mining, ICDM

SP - 924

EP - 929

BT - 2020 [20th] IEEE International Conference on Data Mining (ICDM)

A2 - Plant, Claudia

A2 - Wang, Haixun

A2 - Cuzzocrea, Alfredo

A2 - Zaniolo, Carlo

A2 - Wu, Xindong

PB - Institute of Electrical and Electronics Engineers Inc.

Y2 - 17 November 2020 through 20 November 2020

ER -

Bernardini G, Conte A, Gourdel G, Grossi R, Loukides G, Pisanti N et al. Hide and mine in strings: Hardness and algorithms. In Plant C, Wang H, Cuzzocrea A, Zaniolo C, Wu X, editors, 2020 [20th] IEEE International Conference on Data Mining (ICDM): [Proceedings]. Institute of Electrical and Electronics Engineers Inc. 2021. p. 924-929. 9338348. (Proceedings - IEEE International Conference on Data Mining, ICDM). Epub 2020 Nov 17. doi: 10.1109/ICDM50108.2020.00103

Hide and mine in strings: Hardness and algorithms

Abstract

Publication series

Conference

Bibliographical note

Funding

Keywords

Access to Document

Persistent URL (handle)

Other files and links

Fingerprint

Cite this