A linear-time multivariate micro-aggregation for privacy protection in uniform very large data sets

Agusti Solanas, Roberto Di Pietro

Research output: Chapter in Book/Report/Conference proceedingConference contribution

12 Scopus citations

Abstract

Optimally micro-aggregating a multivariate data set is known to be NP-hard, thus, heuristic approaches are used to cope with this privacy preserving problem. Unfortunately, algorithms in the literature are computationally costly, and this prevents using them on large data sets. We propose a partitioning algorithm to micro-aggregate uniform very large data sets with cost O(n). We provide the mathematical foundations proving the efficiency of our algorithm and we show that the error associated to micro-aggregation is bounded and decreases when the number of micro-aggregated records grows. The experimental results confirm the prediction of the mathematical analysis. In addition, we provide a comparison between our proposal and MDAV, a well-known micro-aggregation algorithm with cost O(n 2). © 2008 Springer Berlin Heidelberg.
Original languageEnglish (US)
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherSpringer Verlag
Pages203-214
Number of pages12
ISBN (Print)3540882685
DOIs
StatePublished - Jan 1 2008
Externally publishedYes

Bibliographical note

Generated from Scopus record by KAUST IRTS on 2023-09-20

Fingerprint

Dive into the research topics of 'A linear-time multivariate micro-aggregation for privacy protection in uniform very large data sets'. Together they form a unique fingerprint.

Cite this