Utility-preserving κ-anonymity

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

[img] [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)


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.

Item Type: Thesis (Masters)
URI: http://research.library.mun.ca/id/eprint/10293
Item ID: 10293
Additional Information: Bibliography: leaves 126-132.
Department(s): Science, Faculty of > Computer Science
Date: 2006
Date Type: Submission
Library of Congress Subject Heading: Computer networks--Security measures; Computer security; Medical records--Access control.

Actions (login required)

View Item View Item


Downloads per month over the past year

View more statistics