Introduction

Imagine a hospital wants to share patient records with researchers. It strips out names and social-security numbers — the obvious identifiers. But the dataset still contains age, ZIP code, and sex. In a landmark 1997 study, Latanya Sweeney showed that those three fields alone could re-identify 87% of the US population from public voter rolls.

The insight behind k-anonymity (formalized by Sweeney and Pierangela Samarati in 1998) is elegantly simple: before releasing a table, generalize the quasi-identifiers — the fields that are not identifiers on their own but become one in combination — until every row is shared by at least k people. With k=3k = 3, knowing someone's age, ZIP, and sex narrows the field to at least three records, so you cannot point to a single person.

The transformation tools are generalization (replace a specific value with a broader category, e.g., age 34 → age range 30–39) and suppression (remove a row or value entirely when it cannot be merged). The goal is to minimize information loss while guaranteeing that no equivalence class — a group sharing the same generalized quasi-identifiers — drops below kk members.

That trade-off between utility and privacy turns out to be computationally hard, and understanding why is a journey straight into P vs NP.

Generalize the Table

Below is a small patient table with three quasi-identifiers: Age, ZIP, and Sex. The sensitive column (Condition) must never be used to re-identify anyone. Use the slider to set k, then press Generalize to watch the table transform until every group of rows with the same quasi-identifiers has at least k members.

<!-- k-anonymity demo — generalize a patient table until every equivalence class has >= k rows -->
<div class="controls">
  <label for="kSlider">k = <strong id="kVal">2</strong></label>
  <input type="range" id="kSlider" min="1" max="5" value="2" />
  <button id="btnGeneralize" type="button">Generalize</button>
  <button id="btnReset" type="button" class="ghost">Reset</button>
</div>
<div class="status" id="status"></div>
<div class="table-wrap">
  <table id="dataTable">
    <thead>
      <tr>
        <th>Age</th>
        <th>ZIP</th>
        <th>Sex</th>
        <th class="sensitive">Condition</th>
      </tr>
    </thead>
    <tbody id="tableBody"></tbody>
  </table>
</div>
<div class="legend">
  <span class="legend-item suppressed-swatch"></span> Suppressed row
  &nbsp;&nbsp;
  <span class="legend-item generalized-swatch"></span> Generalized value
</div>

/* styles for the k-anonymity demo table */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.controls { display: flex; align-items: center; gap: .6rem; flex-wrap: wrap; margin-bottom: .6rem; }
label { font-weight: 600; white-space: nowrap; }
input[type=range] { width: 120px; cursor: pointer; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .85rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.status { font-size: .9rem; font-weight: 600; min-height: 1.3em; margin-bottom: .4rem; }
.status.ok { color: #0a7d33; }
.status.warn { color: #b36200; }
.table-wrap { overflow-x: auto; }
table { border-collapse: collapse; width: 100%; }
th, td { border: 1px solid #cdd9e3; padding: .32rem .6rem; text-align: left; white-space: nowrap; }
th { background: #e8eef3; font-weight: 700; font-size: .82rem; }
th.sensitive { background: #f5e6c8; }
td.sensitive { background: #fdf6e8; }
tr.suppressed td { background: #fce4e4; color: #888; text-decoration: line-through; }
td.gen { background: #ddefff; font-style: italic; }
.legend { display: flex; align-items: center; font-size: .8rem; color: #555; margin-top: .5rem; flex-wrap: wrap; gap: .3rem; }
.legend-item { display: inline-block; width: 14px; height: 14px; border-radius: 3px; vertical-align: middle; }
.suppressed-swatch { background: #fce4e4; border: 1px solid #c92f3c; }
.generalized-swatch { background: #ddefff; border: 1px solid #5a9fd4; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Small patient dataset with quasi-identifiers (age, zip, sex) and one sensitive attribute (condition).
const ORIGINAL = [
  { age: 29, zip: '13053', sex: 'F', cond: 'Flu' },
  { age: 22, zip: '13068', sex: 'M', cond: 'Hypertension' },
  { age: 27, zip: '13053', sex: 'F', cond: 'Flu' },
  { age: 43, zip: '13068', sex: 'M', cond: 'Diabetes' },
  { age: 52, zip: '13068', sex: 'F', cond: 'Hypertension' },
  { age: 47, zip: '13076', sex: 'M', cond: 'Diabetes' },
  { age: 36, zip: '13076', sex: 'F', cond: 'Flu' },
  { age: 32, zip: '13053', sex: 'M', cond: 'Asthma' }
];

// Age generalization: level 0 = exact, level 1 = decade range, level 2 = any.
function generalizeAge(age, level) {
  if (level === 0) return String(age);
  if (level === 1) {
    const lo = Math.floor(age / 10) * 10;
    return lo + '–' + (lo + 9);
  }
  return 'Any';
}

// ZIP generalization: level 0 = exact, level 1 = mask last digit, level 2 = mask last two, level 3 = all masked.
function generalizeZip(zip, level) {
  if (level === 0) return zip;
  if (level === 1) return zip.slice(0, 4) + '*';
  if (level === 2) return zip.slice(0, 3) + '**';
  return '*****';
}

// Sex generalization: level 0 = exact (M/F), level 1 = any.
function generalizeSex(sex, level) {
  if (level === 0) return sex;
  return 'Any';
}

// Equivalence-class key from the three generalized quasi-identifiers.
function qiKey(row) {
  return row.genAge + '|' + row.genZip + '|' + row.genSex;
}

// Greedy k-anonymization — repeatedly generalize the least-generalized attribute until all groups reach size k, then suppress remaining violators.
function greedyAnonymize(k) {
  let rows = ORIGINAL.map(r => ({
    ...r, genAge: String(r.age), genZip: r.zip, genSex: r.sex,
    ageLevel: 0, zipLevel: 0, sexLevel: 0, suppressed: false
  }));

  let changed = true;
  while (changed) {
    changed = false;
    // Count equivalence-class sizes.
    const counts = {};
    rows.forEach(r => { if (!r.suppressed) { const key = qiKey(r); counts[key] = (counts[key] || 0) + 1; } });
    // Find rows whose equivalence class is still below k.
    const violations = rows.filter(r => !r.suppressed && counts[qiKey(r)] < k);
    if (violations.length === 0) break;
    // Generalize the least-generalized quasi-identifier globally (greedy).
    const r0 = violations[0];
    if (r0.ageLevel < 2) {
      const newLevel = r0.ageLevel + 1;
      rows.forEach(r => { if (!r.suppressed) { r.ageLevel = Math.max(r.ageLevel, newLevel); r.genAge = generalizeAge(r.age, r.ageLevel); } });
      changed = true;
    } else if (r0.zipLevel < 3) {
      const newLevel = r0.zipLevel + 1;
      rows.forEach(r => { if (!r.suppressed) { r.zipLevel = Math.max(r.zipLevel, newLevel); r.genZip = generalizeZip(r.zip, r.zipLevel); } });
      changed = true;
    } else if (r0.sexLevel < 1) {
      rows.forEach(r => { if (!r.suppressed) { r.sexLevel = 1; r.genSex = generalizeSex(r.sex, 1); } });
      changed = true;
    } else {
      // All attributes are fully generalized; suppress remaining violators.
      violations.forEach(r => { r.suppressed = true; });
      changed = true;
    }
  }
  return rows;
}

const tbody = document.getElementById('tableBody');
const statusEl = document.getElementById('status');
const kVal = document.getElementById('kVal');
const kSlider = document.getElementById('kSlider');

function renderOriginal() {
  tbody.innerHTML = '';
  ORIGINAL.forEach(row => {
    const tr = document.createElement('tr');
    tr.innerHTML =
      '<td>' + row.age + '</td>' +
      '<td>' + row.zip + '</td>' +
      '<td>' + row.sex + '</td>' +
      '<td class="sensitive">' + row.cond + '</td>';
    tbody.appendChild(tr);
  });
  statusEl.textContent = 'Original table (not yet anonymized).';
  statusEl.className = 'status';
}

function renderAnonymized(rows, k) {
  tbody.innerHTML = '';
  const counts = {};
  rows.forEach(r => { if (!r.suppressed) { const key = qiKey(r); counts[key] = (counts[key] || 0) + 1; } });
  rows.forEach(row => {
    const tr = document.createElement('tr');
    if (row.suppressed) { tr.className = 'suppressed'; }
    const ageGen = row.ageLevel > 0;
    const zipGen = row.zipLevel > 0;
    const sexGen = row.sexLevel > 0;
    tr.innerHTML =
      '<td' + (ageGen && !row.suppressed ? ' class="gen"' : '') + '>' + row.genAge + '</td>' +
      '<td' + (zipGen && !row.suppressed ? ' class="gen"' : '') + '>' + row.genZip + '</td>' +
      '<td' + (sexGen && !row.suppressed ? ' class="gen"' : '') + '>' + row.genSex + '</td>' +
      '<td class="sensitive">' + row.cond + '</td>';
    tbody.appendChild(tr);
  });
  const suppressed = rows.filter(r => r.suppressed).length;
  const remaining = rows.length - suppressed;
  if (suppressed === 0) {
    statusEl.textContent = i18nFmt('%n% rows — every equivalence class has ≥ %k% members. ✓ %k%-anonymous.', { k: k, n: remaining });
    statusEl.className = 'status ok';
  } else {
    statusEl.textContent = i18nFmt('%s% row(s) suppressed. %n% rows remain — %k%-anonymous.', { k: k, s: suppressed, n: remaining });
    statusEl.className = 'status warn';
  }
}

kSlider.addEventListener('input', () => {
  kVal.textContent = kSlider.value;
  renderOriginal();
});

document.getElementById('btnGeneralize').addEventListener('click', () => {
  const k = parseInt(kSlider.value, 10);
  const rows = greedyAnonymize(k);
  renderAnonymized(rows, k);
});

document.getElementById('btnReset').addEventListener('click', () => {
  kSlider.value = 2;
  kVal.textContent = '2';
  renderOriginal();
});

renderOriginal();
Result
Console

Notice that raising k forces broader generalizations — ages collapse into wider ranges, ZIP codes lose digits. The table stays useful at k=2k = 2, but at k=4k = 4 several rows may need to be suppressed entirely. The computer only tried a greedy approach here; finding the optimal generalization that minimizes information loss while guaranteeing kk-anonymity is a problem no algorithm can solve efficiently for all inputs — it's NP-hard.

The Real Complexity

At first glance, k-anonymity looks like a clean optimization problem: generalize quasi-identifiers to minimize distortion while keeping every equivalence class at size ≥k\geq k. How hard can searching a few generalization lattices be?

Very hard, as it turns out:

  • Generalization lattices are exponential. Each attribute has a hierarchy of generalizations (e.g., exact age → decade → all ages). With dd attributes each having hh levels, the search space is hdh^{d} combinations per row, and interactions between attributes multiply the difficulty.
  • NP-hardness was proved in 2004. Andrew Meyerson and Ryan Williams showed that even the simplest version — suppress the minimum number of rows so the remainder is kk-anonymous — is NP-hard. The reduction is from set cover.
  • Suppression alone is NP-hard. If you allow only suppression (no generalization), optimal k-anonymity is still NP-hard for k≥3k \geq 3. This means there is no polynomial-time algorithm that always finds the minimum-suppression solution (unless P = NP).
  • Generalization with suppression is also NP-hard. Allowing the richer generalization operation does not make the problem easier; the search space only grows.

In practice, researchers use heuristics: Datafly, Incognito, Mondrian, and others sacrifice optimality for speed, often guided by an information-loss metric like the normalized certainty penalty. The gap between the greedy solution and the true optimum can be large, and no polynomial-time algorithm is known to close it.

Where It Matters

k-anonymity is not a theoretical curiosity — it shaped how governments and health systems release data:

  • Healthcare: HIPAA's Safe Harbor rule requires suppressing or generalizing 18 categories of identifiers before sharing patient data. k-anonymity provides a formal framework for doing so, and US health agencies use it for public-use files.
  • Census microdata: national statistical offices release individual-level records with quasi-identifiers suppressed or top-coded so that no cell drops below a threshold — precisely k-anonymity in practice.
  • Location privacy: publishing GPS traces without allowing re-identification requires that every trajectory pattern appear in at least kk users, a spatial generalization of the same idea.
  • Beyond k-anonymity: the model has well-known weaknesses — homogeneity attacks (all kk records share the same sensitive value, so knowing someone is in the group reveals their diagnosis) and background-knowledge attacks. These led to stronger models: ℓ\ell-diversity, tt-closeness, and ultimately differential privacy, which provides a mathematical guarantee against any auxiliary-information attack.

The computational hardness of optimal k-anonymity means real systems always make privacy-utility trade-offs under uncertainty — a reminder that privacy is not just a policy question but a computational one.

Conclusion

k-anonymity captures a beautifully human intuition: safety in numbers, anonymity by indistinguishability. Sweeney and Samarati turned it into a rigorous demand — no equivalence class smaller than kk — and that demand turned out to carry genuine computational weight.

Finding the optimal transformation is NP-hard. The heuristics deployed in practice are fast but imperfect, and the gap between what they deliver and the true optimum is unknowable without solving a problem that may take exponential time. Every real deployment of k-anonymity is, at its core, an approximation of an intractable problem.

So the next time you download a "de-identified" dataset, remember that someone — or some heuristic — made a hard call about where to draw the generalization boundary. The line between useful and private passes right through the heart of P vs NP.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/k-anonymity/Content licensed under CC BY-NC 4.0.