How Samarati's Algorithm Achieves K-Anonymity

Imagine this: you are tasked with anonymizing 10 million medical records for a university research project. To prevent linking attacks, you need to apply a masking algorithm like K-Anonymity.

You could take the easy way out and delete all ages, ZIP codes and genders. The data would be anonymous, but the researchers would riot: the dataset would be useless for finding medical correlations. Alternatively, you could try to guess the right amount of blurring (maybe grouping ages by 5 years and leaving the first 3 digits of the ZIP code). But with millions of rows, how do you know if you successfully hid every person without over-blurring the data? Computing every possible combination would take years.

Generalization Lattice

To understand Samarati's algorithm, you must first understand the scale of the problem. For every quasi-identifier (QI) in a dataset, there are multiple levels of generalization.

Take age, for example. The exact age "34" can be generalized to a 5-year bracket ("30-35"), then a 10-year bracket ("30-40"), then a broad category ("Adult") and finally completely suppressed ("*"). If you have multiple QIs like age, ZIP code, gender and job title, the number of possible combinations explodes exponentially.

In computer science, this creates what we call a Domain Generalization Hierarchy (DGH) or a "lattice". At the absolute bottom of the lattice is your raw, unprotected data (high utility, zero privacy). At the absolute top is a completely censored dataset where every value is replaced by a "*" (zero utility, perfect privacy).

The goal is to find the K-Minimal, the lowest point in this lattice that guarantees K-Anonymity. Because there are millions of potential paths through this lattice, finding the optimal one is NP-hard.

Monotonicity and Binary Search

Pierangela Samarati solved this by using a fundamental rule of the lattice: the monotonic property.

Samarati observed that if a specific node in the lattice (a specific combination of generalizations) satisfies K-Anonymity, then every node above it (more generalized) also satisfies K-Anonymity. Conversely, if a node fails the privacy check, everything below it fails too.

Because of this property, Samarati's algorithm doesn't need to check every combination. It uses a binary search: 1. Jump to the Middle: The algorithm determines the total height of the lattice (H) and tests the generalizations exactly in the middle (H/2). 2. Go Down (Less Blurring): If the middle level is successfully k-anonymous, the algorithm knows it can safely explore the lower half of the lattice (H/4) to see if it can salvage even more data utility. 3. Go Up (More Blurring): If the middle level fails to protect the data, the algorithm knows it must search the upper half (3H/4) for a stronger generalization.

By halving the search space at every step, the algorithm rapidly zeroes in on the optimal, K-minimal generalization without wasting time evaluating the entire exponential space.

Tuple Suppression

There is one edge case that can ruin K-Anonymity: outliers. What happens if you have a single 99-year-old patient in a remote ZIP code? To hide that one outlier in a crowd of k people, the algorithm might be forced to blur the entire dataset to an extreme degree (e.g., changing everyone's age to "0-100").

To prevent one outlier from destroying the utility of 10 million records, Samarati's algorithm introduces a MaxSup (Maximum Suppression) threshold.

This allows the system to completely delete (suppress) a tiny, pre-defined maximum number of highly unique rows (tuples). By sacrificing a handful of outliers, the binary search can find a much lower, highly accurate level of generalization for the remaining dataset.

Conclusion

Samarati's algorithm turns an exponential guessing game into a fast binary search with a strong privacy-utility trade-off and it remains one of the core techniques for computing K-Anonymity.

Samarati relies on pre-defined generalization hierarchies (e.g., knowing that "34" belongs in "30-40"), but it isn't the only way to achieve K-Anonymity. In our next article, we will look at a different approach: the Mondrian algorithm.

References

• [1] Samarati, P., "Protecting Respondents' Identities in Microdata Release", IEEE Transactions on Knowledge and Data Engineering (TKDE), 2001.
• [2] Molinari, L., "Elaborato K-Anonimity", 2024.