Hardness of k-anonymous microaggregation

被引：1

作者：

Thaeter, Florian ^{[1
]}

Reischuk, Ruediger ^{[1
]}

机构：

[1] Univ Lubeck, Inst Theoret Informat, D-23562 Lubeck, Germany

来源：

DISCRETE APPLIED MATHEMATICS | 2021年 / 303卷

关键词：

Microaggregation; k-anonymity; Clustering;

D O I：

10.1016/j.dam.2020.10.005

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

k-anonymous microaggregation of data in R-d with d >= 2 is shown to be NP-hard for all k >= 4, extending a previous result for the case k = 3 only. The proof uses similarities between microaggregation and the k-means problem. A reduction of Planar 3-SAT to the k-means clustering problem is adapted to 4-anonymous clustering. Then this construction is extended to arbitrary k >= 4. (C) 2020 Elsevier B.V. All rights reserved.

引用

页码：149 / 158

页数：10

共 11 条

[1] Ordinal, continuous and heterogeneous k-anonymity through microaggregation [J].

Domingo-Ferrer, J ;

Torra, V .

DATA MINING AND KNOWLEDGE DISCOVERY, 2005, 11 (02) :195-212

[2]

Domingo-Ferrer J., 2009, Encyclopedia of Database Systems,, P1736

[3] A polynomial-time approximation to optimal multivariate micro aggregation [J].

Domingo-Ferrer, Josep ;

Sebe, Francesc ;

Solanas, Agusti .

COMPUTERS & MATHEMATICS WITH APPLICATIONS, 2008, 55 (04) :714-732

[4]

Inaba M., 1994, Proceedings of the Tenth Annual Symposium on Computational Geometry, P332, DOI 10.1145/177424.178042

[5] PLANAR FORMULAS AND THEIR USES [J].

LICHTENSTEIN, D .

SIAM JOURNAL ON COMPUTING, 1982, 11 (02) :329-343

[6]

LLOYD SP, 1982, IEEE T INFORM THEORY, V28, P129, DOI 10.1109/TIT.1982.1056489

[7]

Mahajan M, 2009, LECT NOTES COMPUT SC, V5431, P274, DOI 10.1007/978-3-642-00202-1_24

[8]

Micali S., 1980, 21 ANN S FDN COMPUTE, P17

[9]

Oganian A., 2001, STAT J UN EC COMMISS, V18, P345, DOI DOI 10.3233/SJU-2001-18409

[10] A modification of the Lloyd algorithm for k-anonymous quantization [J].

Rebollo-Monedero, David ;

Forne, Jordi ;

Pallares, Esteve ;

Parra-Arnau, Javier .

INFORMATION SCIENCES, 2013, 222 :185-202

← 1 2 →