← All writing

Mondrian Algorithm: The Art of Multidimensional K-Anonymity

May 4, 2026

Privacy

Samarati's algorithm is a solid tool for data privacy, but it applies the same level of generalization to your entire dataset, which can destroy information that didn't need to be touched. The **Mondrian Algorithm** treats data as points in a multidimensional space and recursively slices that space into smaller grids, achieving K-Anonymity with more precision and preserving far more of the underlying data.

Imagine you need to enforce K-Anonymity on a massive medical database. As we discussed in our last article, Samarati's algorithm relies on global recoding. If it decides to generalize the age "34" into the broad bracket "30-40" to hide one specific person in New York, it forces every single 34-year-old in the entire database to be grouped into "30-40" -even if there are thousands of indistinguishable 34-year-olds in California who didn't need that level of masking.

This approach causes unnecessary collateral damage: the dataset becomes more blurred than it needs to be and utility drops sharply as a result.

The Solution: Multidimensional Space

In 2006, LeFevre, DeWitt and Ramakrishnan proposed a much more flexible approach: multidimensional K-Anonymity.

Instead of looking at each Quasi-Identifier (like age, ZIP code or salary) in strict isolation, the Mondrian algorithm treats them as coordinates in a multidimensional space. Every person in your dataset becomes a single point plotted inside a massive, invisible cube.

How the Mondrian Algorithm Works

The algorithm recursively "draws lines" through the dataset to box people together. This is a top-down, "greedy" approach that builds a spatial partitioning structure known as a KD-Tree.

It follows three steps:

  1. The algorithm looks at the entire "box" of data and finds the Quasi-Identifier with the widest spread of normalized values.
  2. It draws a line through the median value of that dimension, splitting the data pool into two smaller boxes.
  3. It checks whether both new boxes contain at least k people. If they do, the algorithm accepts the split and recursively repeats the process on each new box. If a split would leave a box with fewer than k people, it abandons that cut and stops slicing that region.

Once the algorithm can no longer slice any box without violating K-Anonymity, it stops. Every person inside a final box is generalized to match the boundaries of that box.

Because the slicing is dynamic and region-specific, the algorithm can apply different levels of blurring to different groups. It might leave the exact ages of the California patients untouched because they are already hidden in a dense demographic crowd, while applying a broad "30-40" generalization only to the sparse New York patients who actually need it.

Conclusion

Finding the mathematically optimal K-Anonymization map is an NP-Hard problem that would take standard computers years to evaluate. Mondrian's recursive slicing is a shortcut around that: it reaches the required privacy threshold in a fraction of the time and loses less information than global recoding methods like Samarati's.

References

  • [1] LeFevre, K., DeWitt, D. J., & Ramakrishnan, R., "Mondrian Multidimensional K-Anonymity", International Conference on Data Engineering (ICDE), 2006.
  • [2] Molinari, L., "Elaborato K-Anonimity", 2024.