Utility-preserving κ-anonymity

Chaytor, Rhonda (2006) Utility-preserving κ-anonymity. Masters thesis, Memorial University of Newfoundland.

[English] PDF - Accepted Version Available under License - The author retains copyright ownership and moral rights in this thesis. Neither the thesis nor substantial extracts from it may be printed or otherwise reproduced without the author's permission. Download (69MB)

Abstract

As technology advances and more and more person-specific data like health information becomes publicly available, much attention is being given to confidentiality and privacy protection. On one hand, increased availability of information can lead to advantageous knowledge discovery; on the other hand, this information belongs to individuals and their identities must not be disclosed without consent. A recently proposed concept called κ-Anonymity addresses this conflict between doctor-patient confidentiality and society-beneficial research. -- Several κ-Anonymity-based problems have been proposed in the literature; however, these problems do not adequately address preserving utility for the researcher and their algorithms are not computationally efficient. This thesis highlights these inadequacies through a comprehensive overview of previous research, where it is shown that previous solutions lack sufficient ability to meet specific researcher needs. To this end, new utility-preserving problems are proposed and their computational complexities are analyzed. Many results for κ-Anonymity-based problems are systematically derived through this analysis, including two of particular interest: (1) the first known polynomial-time solvable κ-Anonymity-based problem and (2) the first known algorithm-independent polynomial-time approximation intractability results for κ-Anonymity-based problems.

Actions (login required)

View Item