Approximation bounds for minimum information loss microaggregation

Michael J Laszlo; Sumitra Mukherjee

doi:10.1109/tkde.2009.78

Approximation bounds for minimum information loss microaggregation

Research output: Contribution to journal › Article › peer-review

Abstract

The NP-hard microaggregation problem seeks a partition of data points into groups of minimum specified size k, so as to minimize the sum of the squared euclidean distances of every point to its group's centroid. One recent heuristic provides an {\rm O}(k^3) guarantee for this objective function and an {\rm O}(k^2) guarantee for a version of the problem that seeks to minimize the sum of the distances of the points to its group's centroid. This paper establishes approximation bounds for another microaggregation heuristic, providing better approximation guarantees of {\rm O}(k^2) for the squared distance measure and {\rm O}(k) for the distance measure.

Original language	American English
Article number	11
Pages (from-to)	1643-1647
Number of pages	5
Journal	IEEE Transactions on Knowledge and Data Engineering
Volume	21
Issue number	11
DOIs	https://doi.org/10.1109/tkde.2009.78
State	Published - Apr 18 2009

ASJC Scopus Subject Areas

Information Systems
Computer Science Applications
Computational Theory and Mathematics

Keywords

Data security
disclosure control
microdata protection
microaggregation
k-anonymity
approximation algorithms
graph partitioning
information loss
Information loss
Graph partitioning
K-anonymity
Microaggregation
Approximation algorithms
Disclosure control
Microdata protection

Disciplines

Computer Sciences

Access to Document

10.1109/tkde.2009.78

http://dx.doi.org/10.1109/TKDE.2009.78

Cite this

@article{32411e3783704a9994949bfaf35b44e4,

title = "Approximation bounds for minimum information loss microaggregation",

abstract = " The NP-hard microaggregation problem seeks a partition of data points into groups of minimum specified size k, so as to minimize the sum of the squared euclidean distances of every point to its group's centroid. One recent heuristic provides an \{\textbackslash{}rm O\}(k\textasciicircum{}3) guarantee for this objective function and an \{\textbackslash{}rm O\}(k\textasciicircum{}2) guarantee for a version of the problem that seeks to minimize the sum of the distances of the points to its group's centroid. This paper establishes approximation bounds for another microaggregation heuristic, providing better approximation guarantees of \{\textbackslash{}rm O\}(k\textasciicircum{}2) for the squared distance measure and \{\textbackslash{}rm O\}(k) for the distance measure.",

keywords = "Data security, disclosure control, microdata protection, microaggregation, k-anonymity, approximation algorithms, graph partitioning, information loss, Information loss, Graph partitioning, K-anonymity, Microaggregation, Approximation algorithms, Disclosure control, Microdata protection",

author = "Laszlo, \{Michael J\} and Sumitra Mukherjee",

year = "2009",

month = apr,

day = "18",

doi = "10.1109/tkde.2009.78",

language = "American English",

volume = "21",

pages = "1643--1647",

journal = "IEEE Transactions on Knowledge and Data Engineering",

issn = "1558-2191",

publisher = "IEEE Computer Society",

number = "11",

}

TY - JOUR

T1 - Approximation bounds for minimum information loss microaggregation

AU - Laszlo, Michael J

AU - Mukherjee, Sumitra

PY - 2009/4/18

Y1 - 2009/4/18

N2 - The NP-hard microaggregation problem seeks a partition of data points into groups of minimum specified size k, so as to minimize the sum of the squared euclidean distances of every point to its group's centroid. One recent heuristic provides an {\rm O}(k^3) guarantee for this objective function and an {\rm O}(k^2) guarantee for a version of the problem that seeks to minimize the sum of the distances of the points to its group's centroid. This paper establishes approximation bounds for another microaggregation heuristic, providing better approximation guarantees of {\rm O}(k^2) for the squared distance measure and {\rm O}(k) for the distance measure.

AB - The NP-hard microaggregation problem seeks a partition of data points into groups of minimum specified size k, so as to minimize the sum of the squared euclidean distances of every point to its group's centroid. One recent heuristic provides an {\rm O}(k^3) guarantee for this objective function and an {\rm O}(k^2) guarantee for a version of the problem that seeks to minimize the sum of the distances of the points to its group's centroid. This paper establishes approximation bounds for another microaggregation heuristic, providing better approximation guarantees of {\rm O}(k^2) for the squared distance measure and {\rm O}(k) for the distance measure.

KW - Data security

KW - disclosure control

KW - microdata protection

KW - microaggregation

KW - k-anonymity

KW - approximation algorithms

KW - graph partitioning

KW - information loss

KW - Information loss

KW - Graph partitioning

KW - K-anonymity

KW - Microaggregation

KW - Approximation algorithms

KW - Disclosure control

KW - Microdata protection

UR - https://nsuworks.nova.edu/gscis_facarticles/3

UR - http://dx.doi.org/10.1109/TKDE.2009.78

U2 - 10.1109/tkde.2009.78

DO - 10.1109/tkde.2009.78

M3 - Article

SN - 1558-2191

VL - 21

SP - 1643

EP - 1647

JO - IEEE Transactions on Knowledge and Data Engineering

JF - IEEE Transactions on Knowledge and Data Engineering

IS - 11

M1 - 11

ER -

Approximation bounds for minimum information loss microaggregation

Abstract

ASJC Scopus Subject Areas

Keywords

Disciplines

Access to Document

Other files and links

Fingerprint

Cite this