Library Catalog Data Sync Pipelines

K-Anonymity Thresholds for Circulation History Reports

This page answers one narrow operational question: you published a circulation-history report — “titles borrowed by branch and patron age band,” say — and a reviewer noticed that one cell shows a count of 1, tying a single specific title to a single small demographic group, which is enough to re-identify the patron who borrowed it. How do you stop that before the report leaves your hands? It sits under Circulation History Routing & Anonymization, which governs how borrowing events are decoupled from patron identity, and within the broader Patron Validation & Privacy Data Routing architecture. If you publish any aggregate that crosses a title (or subject, or call number) with a demographic breakdown, the thin-cell leak below is one you will eventually ship.

K-anonymity threshold gate over grouped circulation counts Grouped circulation counts keyed by branch, age band and title enter a threshold check that compares each cell's group size against k. Cells whose count is at least k pass straight to release. Cells whose count is below k branch two ways: the generalize path coarsens the quasi-identifier — collapsing age bands or rolling a title up to its subject — and feeds the recomputed group back into the threshold check, while the suppress path removes any cell that still cannot reach k. The release box holds only cells with a group size of at least k, and an append-only audit log at the bottom records every pass, generalize and suppress decision. Grouped counts branch · age band · title → count Threshold check count ≥ k ? quasi-identifier group GENERALIZE coarsen age / roll title up RELEASE count ≥ k, safe to publish SUPPRESS still < k → drop cell Published report every cell ≥ k append-only audit log — every PASS · GENERALIZE · SUPPRESS decision recorded for the released report

Problem Framing

The symptom is not an error — the report renders cleanly and the totals reconcile. The problem is a single cell. Take a pivot of circulation counts keyed by branch, age_band, and title, and scan it for cells small enough to name a person:

text
$ python -m circ_reports.audit --report fall-2026-title-by-agegroup --min-cell 5
branch        age_band   title                                   count
------------  ---------  --------------------------------------  -----
RIVERSIDE     13-17      "Coping With a Parent's Incarceration"      1   <-- re-identifies one teen
RIVERSIDE     65+        "Managing Early-Stage Dementia"             2   <-- two patrons, still thin
CENTRAL       18-24      "The Anarchist Cookbook"                     1   <-- re-identifies one adult
MAIN          25-44      "Intro to Python"                         318
------------  ---------  --------------------------------------  -----
cells below threshold: 3 of 1,204

A count of 1 in the RIVERSIDE / 13-17 row means exactly one teenager at that branch borrowed that title this term. Anyone who knows that a specific 15-year-old uses the Riverside branch — a parent, a caseworker, a nosy neighbor on the library board — can read that person’s borrowing straight off the published table. The title itself is sensitive, which is the worst case, but even a benign title leaks: the cell asserts a fact about a named individual’s reading. The report passed every schema check and every total; the disclosure lives entirely in cells that are too small to be anonymous.

Root Cause

The root cause is the assumption that aggregation is anonymization. It is not. Grouping rows and emitting counts hides the individual rows, but it does nothing about a group of size one — a cell with count 1 is a single row wearing a GROUP BY costume. The quasi-identifier here is the combination (branch, age_band, title): none of those columns is a name, but together they can pick out one person. When the count for a quasi-identifier group is below some threshold k, that cell is effectively a direct disclosure regardless of how the underlying rows were joined or masked upstream.

This is the definition of k-anonymity: a released dataset is k-anonymous when every combination of quasi-identifiers that appears is shared by at least k records, so no individual can be distinguished from at least k − 1 others. A pivot table trivially violates it wherever a cell’s count is less than k. Upstream protections do not save you: even if patron identity was replaced by an HMAC surrogate token before the events reached the reporting store, a count of 1 still re-identifies, because the leak is in the shape of the aggregate, not in any identifier column. Two forces make thin cells routine — sparse collection demand (most titles are borrowed by very few people) and fine-grained demographic breakdowns (narrow age bands multiply the number of groups while shrinking each one). Cross a sparsely borrowed catalog with a fine breakdown and thin cells are the norm, not the exception.

Solution

Enforce a k-anonymity threshold as a mandatory pass over the grouped counts before release. Every cell whose group size is below k is either generalized — coarsen the quasi-identifier (collapse 13-17 and 18-24 into 13-24, or roll a specific title up to its subject) and re-check the merged group — or, if it still cannot reach k, suppressed so the cell never appears. Only cells with a group size of at least k are released. This is a suppression-and-generalization discipline applied inside the circulation-history anonymization boundary, and it fails closed: a cell that cannot be made anonymous is dropped, never published on a guess.

python
from __future__ import annotations

import logging
from collections import defaultdict
from collections.abc import Mapping
from dataclasses import dataclass, field

logger = logging.getLogger("circ_reports.k_anonymity")


class ThresholdError(ValueError):
    """Raised when k is not a usable anonymity threshold."""


# A quasi-identifier cell: (branch, age_band, title) -> patron count.
QuasiKey = tuple[str, str, str]

# Coarser age bands used when a fine band produces a sub-k cell.
AGE_ROLLUP: Mapping[str, str] = {
    "13-17": "13-24",
    "18-24": "13-24",
    "25-44": "25-64",
    "45-64": "25-64",
}


@dataclass(frozen=True)
class KAnonReport:
    released: dict[QuasiKey, int]
    suppressed: list[QuasiKey] = field(default_factory=list)
    generalized: list[QuasiKey] = field(default_factory=list)


def enforce_k_anonymity(
    counts: Mapping[QuasiKey, int],
    *,
    k: int,
    report_id: str,
    subject_of: Mapping[str, str],
) -> KAnonReport:
    """Suppress or generalize every cell whose group size is below k.

    ``counts`` maps (branch, age_band, title) to a patron count. Cells at or
    above ``k`` are released as-is; thin cells are first generalized by
    coarsening the age band and rolling the title up to its subject, and any
    cell that still cannot reach ``k`` is suppressed.
    """
    if k < 2:
        raise ThresholdError(f"k must be >= 2 to provide anonymity, got {k!r}")

    released: dict[QuasiKey, int] = {}
    regrouped: dict[QuasiKey, int] = defaultdict(int)
    generalized: list[QuasiKey] = []

    # Pass 1: release safe cells; funnel thin cells into a coarser grouping.
    for key, count in counts.items():
        if count >= k:
            released[key] = count
            continue
        branch, age_band, title = key
        coarse: QuasiKey = (
            branch,
            AGE_ROLLUP.get(age_band, age_band),
            subject_of.get(title, title),
        )
        regrouped[coarse] += count
        generalized.append(key)
        logger.info(
            "cell_generalized",
            extra={"report_id": report_id, "cell": key, "count": count, "k": k},
        )

    # Pass 2: release generalized cells that now clear k; suppress the rest.
    suppressed: list[QuasiKey] = []
    for key, count in regrouped.items():
        if count >= k:
            released[key] = released.get(key, 0) + count
        else:
            suppressed.append(key)
            logger.warning(
                "cell_suppressed",
                extra={"report_id": report_id, "cell": key, "count": count, "k": k},
            )

    return KAnonReport(
        released=released, suppressed=suppressed, generalized=generalized
    )

The behavioural change is that release is now conditional on group size. The RIVERSIDE / 13-17 / "Coping With a Parent's Incarceration" cell with count 1 no longer appears verbatim; it is folded into a coarser RIVERSIDE / 13-24 / <subject> group, and it is published only if that merged group reaches k. If it still cannot — a genuinely rare title in a small branch — it is suppressed and logged, never guessed at. Note the fail-closed default in pass 2: anything that survives generalization without reaching k lands in suppressed, so no sub-k cell can slip through.

This is deliberately a different mechanism from the noise-based approach in Implementing Differential Privacy for Patron Analytics. Differential privacy leaves every cell in place but perturbs its value with calibrated random noise, spending a privacy budget as it goes; k-anonymity keeps counts exact but changes the table’s shape by removing or merging cells. Prefer k-anonymity when consumers need exact, reconcilable counts and can tolerate missing rows — a compliance extract, a board report — and reach for the noise mechanism when you must publish every cell and can tolerate approximate values. They compose: you can generalize to a k-anonymous grouping first, then add noise to the surviving counts.

Compliance or Privacy Impact

Enforcing the threshold changes the privacy posture of every published circulation report in a few concrete ways.

The threshold narrows what a report can say, and that is the point: a suppressed cell is information you were never entitled to publish about an individual. The risk shifts onto the correctness of k and the quasi-identifier list, so both deserve code review whenever a new demographic column is added to a report.

Verification

Confirm the gate with a test that asserts no released cell is below k and that a thin cell which cannot be generalized to k is suppressed rather than emitted.

python
import pytest

from circ_reports.k_anonymity import ThresholdError, enforce_k_anonymity

SUBJECT_OF = {
    "Coping With a Parent's Incarceration": "Family / Social Issues",
    "Managing Early-Stage Dementia": "Health / Aging",
}


def test_no_released_cell_is_below_k() -> None:
    counts = {
        ("RIVERSIDE", "13-17", "Coping With a Parent's Incarceration"): 1,
        ("RIVERSIDE", "18-24", "Coping With a Parent's Incarceration"): 1,
        ("MAIN", "25-44", "Intro to Python"): 318,
    }
    report = enforce_k_anonymity(
        counts, k=5, report_id="test", subject_of=SUBJECT_OF
    )

    # Every published cell clears the threshold.
    assert all(count >= 5 for count in report.released.values())
    # The two thin teen cells never appear verbatim.
    assert ("RIVERSIDE", "13-17", "Coping With a Parent's Incarceration") \
        not in report.released
    # They merged but still could not reach k, so they were suppressed.
    assert report.suppressed
    assert ("MAIN", "25-44", "Intro to Python") in report.released


def test_rejects_meaningless_threshold() -> None:
    with pytest.raises(ThresholdError):
        enforce_k_anonymity({}, k=1, report_id="test", subject_of={})

For a running pipeline, add a release-time invariant: before any report is written to its published location, assert all(v >= k for v in released.values()) and refuse to emit the file otherwise — the same fail-closed reflex the gate applies per cell, applied to the report as a whole. Track the suppression rate over time; a sudden jump after a schema change is your signal that a new demographic column made the breakdown too fine and the quasi-identifier list needs a reviewed update.