2020-11-17
Hide and mine in strings: Hardness and algorithms
Publication
Publication
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.
| Additional Metadata | |
|---|---|
| , , , , | |
| doi.org/10.1109/ICDM50108.2020.00103 | |
| 20th IEEE International Conference on Data Mining, ICDM 2020 | |
| Networks | |
| Organisation | Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands |
|
Bernardini, G., Conte, A., Gourdel, G., Grossi, R., Loukides, G., Pisanti, N., … Sweering, M. (2020). Hide and mine in strings: Hardness and algorithms. In 20th IEEE International Conference on Data Mining (pp. 924–929). doi:10.1109/ICDM50108.2020.00103 |
|
