Contrained Generalization For Data Anonymization - A Systematic Search Based Approach

Data generalization is a powerful technique for sanitizing multi-attribute data for publication. In a multidimensional model, a subset of attributes called the quasi-identifiers (QI) are used to define the space and a generalization scheme corresponds to a partitioning of the data space. The process of sanitization can be modeled as a constrained optimization problem where the information loss metric is to be minimized while ensuring that the privacy criteria are enforced. The privacy requirements translate into constraints on the partitions (bins), like minimum occupancy constraints for k-anonymity, value diversity constraint for l-diversity etc. Most algorithms proposed till date use some greedy search heuristic to search for a locally optimal generalization scheme. The performance of such algorithms degrade rapidly as the constraints are made more complex and numerous. To address this issue, in this paper we develop a complete enumeration based systematic search framework that searches for the globally optimal generalization scheme amongst all feasible candidates. We employ a novel enumeration technique that eliminates duplicates and develop effective pruning heuristics that cut down the solution space in order to make the search tractable. Our scheme is versatile enough to accommodate multiple constraints and information loss functions satisfying a set of generic properties (that are usually satisfied by most metrics proposed in literature). Additionally, our approach allows the user to specify various stopping criteria and can give a bound on the approximation factor achieved by any candidate solution. Finally, we carry out extensive experimentation whose results illustrate the power of our algorithm and its advantage over other competing approaches.