Generalization Hierarchy

These taxonomies map specific values to broader categories within a single attribute domain, forming the backbone of attribute suppression.

• Numerical Hierarchies: Continuous values (e.g., age) are partitioned into intervals. A value of 27 might generalize to [25-30], then [20-30], then [20-40].
• Categorical Hierarchies: Discrete values are mapped to parent categories. A specific ZIP code 53703 generalizes to Madison, then Wisconsin, then Midwest.
• Semantic Integrity: Each step must preserve analytical meaning; a city cannot generalize to a nonsensical category that breaks geographic analysis.

The hierarchy dictates the granularity of the transformation applied to quasi-identifiers to achieve a target k value.

• Full-Domain Generalization: The strictest approach. If one value in an attribute is generalized to a level, all values of that attribute must be generalized to the same level in the hierarchy.
• Cell Suppression: Instead of generalizing, specific outlier values that prevent k-anonymity are simply removed or replaced with a null marker.
• Trade-off: Full-domain generalization preserves uniformity for analysis but causes high information loss. Suppression retains precision for most records but creates missing data.

The origin of the taxonomy impacts both the accuracy and the automation of the de-identification pipeline.

• Predefined Taxonomies: Expert-curated trees (e.g., ICD medical codes, NAICS industry codes) that guarantee semantic correctness and regulatory compliance.
• Dynamic Value Generalization: Algorithmically generated hierarchies based on data distribution, often using clustering or interval merging to minimize information loss.
• Hybrid Approach: Using a predefined semantic tree for categorical attributes while dynamically binning numerical attributes based on density.

A formal framework representing all possible combinations of generalization levels across multiple quasi-identifiers as a mathematical lattice.

• State Space: Each node in the lattice represents a specific generalization strategy (e.g., Age=Level 2, ZIP=Level 1).
• Optimal Search: Algorithms traverse this lattice to find the minimal generalization required to achieve k-anonymity, directly minimizing information loss.
• Predictive Taxonomies: The lattice defines the legal moves allowed during optimization, preventing invalid or semantically broken combinations.

The depth of the hierarchy directly controls the precision of the sanitized data. A shallow tree over-generalizes; a deep tree risks re-identification.

• Coarse Granularity: High privacy, low utility. Example: Generalizing all ages to a single bucket [0-100] guarantees anonymity but destroys demographic analysis.
• Fine Granularity: Low privacy, high utility. Example: Generalizing ages to [25-26] may fail to achieve k-anonymity if few people share that exact range.
• The Sweet Spot: The hierarchy must be deep enough to allow the algorithm to find the exact level where k is satisfied without collapsing the data into useless categories.

Operationalizing a hierarchy requires strict metadata management to map raw columns to their generalization functions.

• Attribute Binding: Each quasi-identifier column in the schema must be explicitly linked to its specific hierarchy file or function.
• Version Control: Hierarchies evolve over time (e.g., ZIP code changes). The specific version used must be logged in the data lineage for audit reproducibility.
• Null Handling: The hierarchy must define a policy for missing values—whether they are suppressed, treated as a distinct category, or generalized to the root node.

A foundational privacy model ensuring each record is indistinguishable from at least k-1 other records regarding quasi-identifiers. Generalization hierarchies are the primary mechanism to achieve this by replacing specific values with broader categories until equivalence classes of size k are formed.

• Prevents singling out individuals
• Uses domain generalization hierarchies to define allowed transformations
• Susceptible to homogeneity attacks without extensions

An extension of k-anonymity requiring each equivalence class to contain at least l well-represented values for sensitive attributes. Generalization hierarchies are applied to quasi-identifiers, but l-diversity ensures the sensitive attribute within each group is diverse enough to resist homogeneity attacks.

• Distinct l-diversity: at least l distinct values
• Entropy l-diversity: entropy of sensitive values ≥ log(l)
• Recursive (c,l)-diversity: limits frequency of most common value

A privacy model requiring the distribution of a sensitive attribute in any equivalence class to be within a threshold t of its global distribution. This prevents skewness attacks where an attacker infers information from the distributional difference itself.

• Uses Earth Mover's Distance to measure distributional distance
• Generalization hierarchies define the QID groupings
• Stronger than l-diversity but reduces utility more aggressively

A set of non-sensitive attributes that, when combined with external data, can uniquely or nearly uniquely identify an individual. Generalization hierarchies are built specifically for QID attributes to systematically reduce their granularity.

• Common QIDs: date of birth, ZIP code, gender
• Identified through linkage attacks with public datasets
• The hierarchy defines the allowable generalization path from specific to general

The complete removal of an entire column from a dataset when generalization alone cannot achieve the desired privacy guarantee. This is the most extreme level in a generalization hierarchy, where the value is replaced with a suppressed token or removed entirely.

• Applied when outlier records resist generalization
• Reduces dimensionality of the dataset
• Trade-off: maximum privacy at the cost of analytical utility

An alternative to generalization that intentionally alters original values through noise addition, swapping, or rounding. While generalization hierarchies replace values with broader categories, perturbation modifies values while preserving statistical distributions.

• Includes microaggregation and rank swapping
• Often combined with generalization in hybrid approaches
• Preserves aggregate statistics better than suppression