Title :
On Multidimensional k-Anonymity with Local Recoding Generalization
Author :
Yang Du ; Tian Xia ; Yufei Tao ; Donghui Zhang ; Feng Zhu
Author_Institution :
Coll. of Comput. & Inf. Sci., Northeastern Univ., Boston, MA, USA
Abstract :
This paper presents the first theoretical study, on using local-recoding generalization (LRG) to compute a k-anonymous table with quality guarantee. First, we prove that it is NP-hard both to find the table with the maximum quality, and to discover a solution with an approximation ratio at most 5/4. Then, we develop an algorithm with good balance between the approximation ratio and time complexity. The quality of our solution is verified by experiments.
Keywords :
computational complexity; data privacy; NP-hard; local recoding generalization; multidimensional k-anonymity; quality guarantee; time complexity; Approximation algorithms; Data mining; Data privacy; Databases; Educational institutions; Multidimensional systems; Polynomials; Protection; Publishing; Remuneration;
Conference_Titel :
Data Engineering, 2007. ICDE 2007. IEEE 23rd International Conference on
Conference_Location :
Istanbul
Print_ISBN :
1-4244-0802-4
DOI :
10.1109/ICDE.2007.369026
