Optimization-based k-anonymity algorithms. Issue 93 (June 2020)

• Record Type: Journal Article
• Authors: Liang, Yuting; Samavi, Reza
• Is Part Of: Computers & security. Issue 93(2020)
• Publication Date: 2020-06
• Subjects: Anonymization -- Optimization -- Privacy -- Security -- Mixed Integer Linear Program; Computer security -- Periodicals; Electronic data processing departments -- Security measures -- Periodicals; 005.805
• DOI: 10.1016/j.cose.2020.101753
• Languages: English
• ISSNs: 0167-4048

Abstract

Abstract: In this paper we present a formulation of k -anonymity as a mathematical optimization problem. In solving this formulated problem, k -anonymity is achieved while maximizing the utility of the resulting dataset. Our formulation has the advantage of incorporating different weights for attributes in order to achieve customized utility to suit different research purposes. The resulting formulation is a Mixed Integer Linear Program (MILP), which is NP-complete in general. Recognizing the complexity of the problem, we propose two practical algorithms which can provide near-optimal utility. Our experimental evaluation confirms that our algorithms are scalable when used for datasets containing large numbers of records.