Optimization-based k-anonymity algorithms

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 orde...

Full description

Saved in:
Bibliographic Details
Published in:Computers & security 2020-06, Vol.93, p.101753-18, Article 101753
Main Authors: Liang, Yuting, Samavi, Reza
Format: Article
Language:English
Subjects:
Algorithms
Anonymization
Datasets
Linear programming
Mixed integer
Mixed Integer Linear Program
Optimization
Privacy
Security
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0167-4048
1872-6208
DOI:10.1016/j.cose.2020.101753