To access the full text documents, please follow this link:

An Algorithm for k-Anonymous Microaggregation and Clustering Inspired by the Design of Distortion-Optimized Quantizers
Forné Muñoz, Jorge; Soriano Ibáñez, Miguel
Universitat Politècnica de Catalunya. Departament d'Enginyeria Telemàtica; Universitat Politècnica de Catalunya. SERTEL - Serveis Telemàtics
We present a multidisciplinary solution to the problems of anonymous microaggregation and clustering, illustrated with two applications, namely privacy protection in databases, and private retrieval of location-based information. Our solution is perturbative, is based on the same privacy criterion used in microdata k-anonymization, and provides anonymity through a substantial modification of the Lloyd algorithm, a celebrated quantization design algorithm, endowed with numerical optimization techniques. Our algorithm is particularly suited to the important problem of k-anonymous microaggregation of databases, with a small integer k representing the number of individual respondents indistinguishable from each other in the published database. Our algorithm also exhibits excellent performance in the problem of clustering or macroaggregation, where k may take on arbitrarily large values. We illustrate its applicability in this second, somewhat less common case, by means of an example of location-based services. Specifically, location-aware devices entrust a third party with accurate location information. This party then uses our algorithm to create distortion-optimized, size-constrained clusters, where k nearby devices share a common centroid location, which may be regarded as a distorted version of the original one. The centroid location is sent back to the devices, which use it when contacting untrusted location-based information providers, in lieu of the exact home location, to enforce k-anonymity. We compare the performance of our novel algorithm to the state-of-the-art microaggregation algorithm MDAV, on both synthetic and standardized real data, which encompass the cases of small and large values of k. The most promising aspect of our proposed algorithm is its capability to maintain the same k-anonymity constraint, while outperforming MDAV by a significant reduction in data distortion, in all the cases considered.
Peer Reviewed
Àrees temàtiques de la UPC::Enginyeria electrònica i telecomunicacions::Telemàtica i xarxes d'ordinadors::Protocols de comunicació
Multivariate analysis
Anàlisi multivariable
Attribution-NonCommercial-NoDerivs 3.0 Spain
Article - Draft
Elsevier Science Ltd.

Show full item record

Related documents

Other documents of the same author

Muñoz Tapia, José Luis; Forné Muñoz, Jorge; Esparza Martín, Óscar; Soriano Ibáñez, Miguel
Zarza, Luis; Forné Muñoz, Jorge; Pegueroles Vallés, Josep R.; Soriano Ibáñez, Miguel
Muñoz Tapia, José Luis; Forné Muñoz, Jorge; Esparza Martín, Óscar; Soriano Ibáñez, Miguel
Rebollo Monedero, David; Bartoli, Andrea; Hernández Serrano, Juan; Forné Muñoz, Jorge; Soriano Ibáñez, Miguel
Esparza Martín, Óscar; Muñoz Tapia, José Luis; Tomàs Buliart, Joan; Soriano Ibáñez, Miguel