Greedy partitioning,
one cut at a time
Mondrian splits a table recursively on the quasi-identifiers until no further cut keeps every part large enough. Walk through every iteration on a 10-patient table, first for k-anonymity, then for l-diversity.
The table
Shaded purple: quasi-identifiers (QI). Shaded orange: sensitive attribute.
The algorithm
Anonymize(partition) if (no allowable multidimensional cut for partition) return φ : partition → summary else dim ← choose_dimension() fs ← frequency_set(partition, dim) splitVal ← find_median(fs) lhs ← {t ∈ partition : t.dim ≤ splitVal} rhs ← {t ∈ partition : t.dim > splitVal} return Anonymize(rhs) ∪ Anonymize(lhs)
How each line is applied
- choose_dimension: the quasi-identifier with the widest normalized range. Age: (max − min) / 12. Sex and City use the order Female < Male and Rotterdam < Utrecht < Zwolle. Ties go to Age, then Sex, then City.
- frequency_set: each value of the dimension in the partition with its count.
- find_median(fs): the median of the partition on that dimension, where every record counts. Using the frequency set: (1) add all counts to get n; (2) the median is record p = ⌊(n − 1)/2⌋ + 1; (3) go through the values in order, adding their counts; the first value whose running count reaches p is the median. Example for Age on the whole table: fs = 16:1, 18:1, 19:1, 22:2, 23:1, 24:1, 25:1, 26:1, 28:1, so n = 10 and p = 5. Running counts 1, 2, 3, 5 reach 5 at 22, so splitVal = 22.
- Allowable cut: lhs and rhs each have at least k records. In the l-diversity tab, each side must also have at least l distinct diseases. If the cut on the chosen dimension is not allowable, the next dimension is tried; if none is allowable, the partition is final.
- Recursion: the LHS is processed first, then the RHS, so iteration numbers follow the partition tree from left to right.
- φ: each final partition is published with the min–max range of each quasi-identifier.
Make the table k-anonymous
Pick k, then step through the recursion. Each iteration handles one partition: measure the ranges, pick a dimension, find the median, and test whether the cut is allowable.
Partition tree
Select a partition to jump to its iteration.
The k-anonymous release
Each final partition is published with min–max ranges on the QIs. "*" means the range covers the whole domain.
Make it l-diverse
k-anonymity hides who is who, but a class where everyone has the same disease still leaks it. Distinct l-diversity requires at least l different diseases in every class. First check the k-anonymous table; if it fails, run Mondrian again with l added to the allowable-cut rule.
Step A: check the k-anonymous table
Does it work?
Answers for the k and l you picked, then every combination at once.
All combinations
"As is": the k-anonymous table already meets l. "Re-partition": Mondrian must be rerun with l in the cut rule. "Single class": no cut is allowable, so the whole table is one class. "Not applicable": even the whole table can't satisfy the requirement.