Fast Data Anonymization with Low Information Loss

Gabriel Ghinita, Panagiotis Karras, Panos Kalnis, Nikos MamoulisVLDB 2007 · OpenReview

Introduction

In the era of big data, sharing sensitive microdata—such as medical records or financial transactions—is essential for research and policy-making. However, removing direct identifiers like names and social security numbers is insufficient to protect privacy. Individuals can often be re-identified by linking "quasi-identifiers" (QI), such as Age, ZIP code, and Gender, to external public databases. This paper, originally presented at VLDB 2007, introduces a high-performance framework designed to anonymize large-scale datasets efficiently while minimizing the loss of data utility.

The Privacy Challenge: $k$-Anonymity and $\ell$-Diversity

To safeguard privacy, two primary models are widely used:

  1. $k$-Anonymity: This requires that each record in a released dataset be indistinguishable from at least $k-1$ other records based on its quasi-identifiers.
  2. $\ell$-Diversity: A more robust model that addresses the limitations of $k$-anonymity by ensuring that sensitive attributes (e.g., a specific medical diagnosis) are sufficiently diverse within each anonymous group. This prevents attackers from using background knowledge to infer sensitive information.
Original microdata table showing Age, Weight, Disease, and the corresponding 1D mapping values.

The core difficulty lies in the "curse of dimensionality." Finding an optimal partitioning of multi-dimensional data that satisfies these privacy constraints while minimizing information loss is an NP-hard problem. Traditional methods, such as the "Mondrian" recursive partitioning algorithm, often produce coarse groupings that significantly degrade data quality for analytical purposes.

Methodology: The 1D Transformation

The authors propose a novel approach: mapping multi-dimensional quasi-identifiers into a single dimension (1D) using space-filling curves, specifically the Hilbert curve. This transformation leverages the property of "locality preservation," where points close together in multi-dimensional space remain close on the 1D line.

Comparison of k-anonymous groups (b), the 1D mapping concept (c), and the resulting l-diverse groups (d).

Optimal 1D $k$-Anonymity

Once the data is projected into 1D, the problem of optimal partitioning becomes tractable. The authors demonstrate that the optimal $k$-anonymous grouping can be found using a Dynamic Programming (DP) approach. By restricting the search to a small window of records (between $k$ and $2k-1$), the algorithm achieves linear time complexity, $O(N)$, making it suitable for massive datasets.

Heuristic 1D $\ell$-Diversity

$\ell$-diversity is inherently more complex because groups may need to overlap to satisfy diversity requirements. The authors developed a linear-time heuristic based on theoretical properties such as Group Order and Border Order. This heuristic allows for efficient grouping in 1D that translates back into high-quality, diverse clusters in the original multi-dimensional space.

Evaluation and Results

The framework was evaluated using the standard ADULT and CENSUS datasets, the latter containing 500,000 records. The authors utilized the Global Certainty Penalty (GCP) metric to quantify information loss, which measures the "area" or "volume" covered by generalized groups.

Key Performance Metrics

  • Information Loss: The Hilbert-based method consistently outperformed state-of-the-art techniques like Mondrian and TopDown clustering. In many scenarios, it reduced information loss by a factor of 2 to 3, preserving much higher data utility for subsequent analysis.
  • Scalability: The performance gains were dramatic. For the 400,000-record CENSUS dataset, the proposed method completed anonymization in approximately 40 seconds. In contrast, TopDown clustering required nearly 6 hours to process the same data.
  • Analytical Accuracy: In Online Analytical Processing (OLAP) query tests, the anonymized data produced by this method was up to two orders of magnitude more accurate than that produced by Mondrian, particularly under $\ell$-diversity constraints.

Conclusion

By simplifying multi-dimensional privacy problems into 1D space-mapping tasks, this research provides a scalable and effective solution for data anonymization. The use of Hilbert curves ensures that spatial proximity is maintained, leading to significantly lower information loss than previous axis-parallel splitting methods. Future work includes exploring the "dual problem" of maximizing privacy for a fixed utility budget and extending these techniques to real-time streaming data environments.

Summary updated

BibTeX
@inproceedings{ghinita2007fast,
  author = {Gabriel Ghinita and Panagiotis Karras and Panos Kalnis and Nikos Mamoulis},
  title = {{Fast Data Anonymization with Low Information Loss}},
  booktitle = {VLDB},
  year = {2007},
  url = {https://openreview.net/forum?id=cB3DIAqMhM},
}
Figure