Full Citation

Title: The Hardness and Approximation Algorithms for L-Diversity

Citation Type: Miscellaneous

Publication Year: 2009

ISBN:

ISSN:

DOI:

NSFID:

PMCID:

PMID:

Abstract: The existing solutions to privacy preserving publication can beclassified into the theoretical and heuristic categories. The formerguarantees provably low information loss, whereas the latterincurs gigantic loss in the worst case, but is shown empirically toperform well on many real inputs. While numerous heuristic algorithmshave been developed to satisfy advanced privacy principlessuch as l-diversity, t-closeness, etc., the theoretical category is currentlylimited to k-anonymity which is the earliest principle knownto have severe vulnerability to privacy attacks. Motivated by this,we present the first theoretical study on l-diversity, a popular principlethat is widely adopted in the literature. First, we show thatoptimal l-diverse generalization is NP-hard even when there areonly 3 distinct sensitive values in the microdata. Then, an (l d)-approximation algorithm is developed, where d is the dimensionalityof the underlying dataset. This is the first known algorithmwith a non-trivial bound on information loss. Extensive experimentswith real datasets validate the effectiveness and efficiency ofproposed solution.

User Submitted?: No

Authors: Yi, Ke; Tao, Yufei; Xiao, Xiaokui

Publisher: Nanyang Technological University

Data Collections: IPUMS USA

Topics: Methodology and Data Collection, Other

Countries: