COE 526 Mondrian lab
Course home
COE 526 · Data anonymization lab

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

  1. 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.
  2. frequency_set: each value of the dimension in the partition with its count.
  3. 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.
  4. 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.
  5. Recursion: the LHS is processed first, then the RHS, so iteration numbers follow the partition tree from left to right.
  6. φ: each final partition is published with the min–max range of each quasi-identifier.

Part 1

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.

k =

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.

Part 2

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.

k =
l =

Step A: check the k-anonymous table

Part 3

Does it work?

Answers for the k and l you picked, then every combination at once.

k =
l =

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.

What to take away