Protecting Respondents' Identities in Microdata Release

Pierangela Samarati

article2001TKDE2,525 citations

Establishes the foundational model of k-anonymity against linking attacks and introduces an efficient binary search algorithm over generalization lattices to release truthful microdata using minimal generalization and suppression.

Listen

The article addresses the growing need to release detailed microdata from sources such as census surveys, health organizations, and government agencies while protecting the identities of the individuals described. Explicit identifiers like names and Social Security numbers are routinely removed, yet combinations of other attributes—race, birth date, sex, and ZIP code—can still serve as quasi-identifiers that link released records to publicly available data such as voter lists, enabling re-identification and unintended disclosure of sensitive information. This risk has become acute because of widespread electronic data availability and increased computational power for linking attacks, especially in medical and financial domains.

The work sets out to provide a formal foundation for releasing microdata that satisfies a quantifiable anonymity requirement. It defines k-anonymity as the property that every combination of values on a quasi-identifier appears at least k times in the released table, thereby ensuring that each record can be linked to at least k individuals. The article shows how generalization of attribute values and selective suppression of tuples can enforce this property while preserving the truthfulness of every released fact.

The approach begins by modeling generalization hierarchies for each attribute domain and representing possible generalizations as paths in a lattice of distance vectors. An algorithm performs a binary search over the height of this lattice to locate a k-minimal generalization that meets the anonymity requirement and stays within a user-specified suppression threshold. Suppression is applied only to the minimal set of outlier tuples needed at the chosen generalization level. The method operates on the projection of the private table onto the quasi-identifier and produces a unique minimal-suppression table for any given distance vector.

Key findings demonstrate that multiple k-minimal generalizations may exist for a given table and k value; the algorithm returns one of lowest absolute distance. Suppression and generalization are complementary: allowing a modest number of tuple suppressions (for example, one or two records) can avoid large increases in generalization depth. Preference policies such as minimum absolute or relative distance, maximum tuple diversity, or minimum suppression can then be applied to select among candidate minimal solutions. The framework also shows that k-anonymity cannot be guaranteed by checking only two- or three-way attribute combinations, a limitation of earlier heuristic systems.

These results matter because they enable organizations to release truthful microdata for research and analysis with provable privacy guarantees, avoiding the distortions introduced by noise-addition or swapping techniques. Decision makers can balance data utility against privacy by choosing k, the suppression threshold, and a preference policy that reflects the intended use of the data.

Next steps include implementing efficient algorithms for large tables, extending the model to handle updates, multiple releases, and collusion risks, and exploring cell-level suppression and finer-grained preference constraints. The main limitations are the assumption of a single static quasi-identifier and the requirement that the original table already contains at least k records; further work is needed before the approach can be applied confidently to dynamic or multi-table environments.

University of Milan asian continental ancestry group computational power efficient algorithm microdata release statistical disclosure control anonymity requirement

Samarati (2001).pdf

Paper: Efficient algorithms for mining outliers from large data sets, S. Ramaswamy et al. (2000). Presents foundational distance-based k-nearest-neighbor formulations that provide essential context for identifying sparse outlier records targeted for tuple suppression in microdata anonymization.
Paper: LOF: identifying density-based local outliers, Markus M. Breunig et al. (2000). Introduces density-based local outlier scoring, which underpins the logic of detecting sparse, highly identifiable points in multi-attribute data.
Paper: Data Mining: An Overview from a Database Perspective, Ming-Syan Chen et al. (1996). Surveys core relational data mining algorithms and lattice-based search strategies that informed systematic generalization hierarchy traversals in relational tables.

Paper: Deep Learning with Differential Privacy, Martín Abadi et al. (2016). Extends formal privacy guarantees beyond table-level generalization and suppression to rigorous differential privacy mechanisms applied directly during model training.
Paper: Membership Inference Attacks Against Machine Learning Models, Reza Shokri et al. (2016). Demonstrates membership inference attacks against released statistical and predictive models, analyzing downstream re-identification risks that persist when raw microdata releases are replaced by model interfaces.
Paper: Extracting Training Data from Large Language Models, Nicholas Carlini et al. (2020). Illustrates how modern models inadvertently memorize and expose unique verbatim records, demonstrating contemporary disclosure risks analogous to microdata quasi-identifier linkage.
Paper: Large-scale online deanonymization with LLMs, Simon Lermen et al. (2026). Shows how modern language models automate cross-domain quasi-identifier linkage attacks at scale over unstructured text, extending the classical structured record linkage threat model.
Paper: Federated Machine Learning, Qiang Yang et al. (2019). Applies decentralized collaborative computing to train models across isolated data silos without releasing or centralizing sensitive microdata.

Cover for Protecting Respondents' Identities in Microdata Release

Abstract

Today’s globally networked society places great demand on the dissemination and sharing of information. While in the past released information was mostly in tabular and statistical form, many situations call today for the release of specific data (microdata). In order to protect the anonymity of the entities (called respondents) to which information refers, data holders often remove or encrypt explicit identifiers such as names, addresses, and phone numbers. De-identifying data, however, provides no guarantee of anonymity. Released information often contains other data, such as race, birth date, sex, and ZIP code, that can be linked to publicly available information to re-identify respondents and inferring information that was not intended for disclosure.

In this paper we address the problem of releasing microdata while safeguarding the anonymity of the respondents to which the data refer. The approach is based on the definition of k-anonymity. A table provides k-anonymity if attempts to link explicitly identifying information to its content map the information to at least k entities. We illustrate how k-anonymity can be provided without compromising the integrity (or truthfulness) of the information released by using generalization and suppression techniques. We introduce the concept of minimal generalization that captures the property of the release process not to distort the data more than needed to achieve k-anonymity, and present an algorithm for the computation of such a generalization. We also discuss possible preference policies to choose among different minimal generalizations.

Topics

asian continental ancestry group computational power efficient algorithm microdata sensitive informations anonymous communication unlinkability user preferences individual privacy tabu search

Keywords

microdata release statistical disclosure control anonymity requirement disclosure limitation quasi-identifiers explicit identifiers domain generalization statistical databases

Index terms:
1 Introduction
2 Assumptions and preliminary definitions
3 Generalizing data
3.1 Generalization relationships
3.2 Generalized table and minimal generalization
4 Suppressing data
5 Computing a k-minimal generalization
Find_vector
6 Preferences
7 Related work
8 Conclusions
Acknowledgments
References

Knowls

Knowl 1 — Definition of k-Anonymity and Quasi-Identifiers
definition
Let $PT$ be a private table containing microdata where each tuple represents at most one respondent, and explicit identifiers (e.g., names, Social Security numbers) have been removed or encrypted. A quasi-identifier $QI = \{A_1, \dots, A_n\}$ is a set of attributes in $PT$ that, in combination, can be linked with external information to re-identify respondents.

A table $T(A_1, \dots, A_m)$ satisfies $k$ -anonymity with respect to quasi-identifier $QI \subseteq \{A_1, \dots, A_m\}$ if and only if each distinct sequence of values in the projection $T[QI]$ appears with at least $k$ occurrences in $T[QI]$ , where $k \ge 1$ is an integer anonymity parameter.

Under the condition that all attributes in $PT$ externally available in combination to a recipient are contained in $QI$ , satisfying $k$ -anonymity guarantees that linking released data with external tables matches each released tuple indistinctly to at least $k$ individuals in the population.
Knowl 2 — Domain and Value Generalization Hierarchies and Domain Tuple Lattice
definition
Generalization replaces attribute values with broader, less specific representations. For each ground attribute domain $D$ , a set of generalized domains $\mathrm{Dom}$ is structured by a generalization relation $\le_D$ satisfying:
1. $\forall D_i, D_j, D_z \in \mathrm{Dom} : (D_i \le_D D_j \wedge D_i \le_D D_z) \implies (D_j \le_D D_z \vee D_z \le_D D_j)$ , ensuring that every domain has at most one direct generalization and yielding a totally ordered domain generalization hierarchy $\mathrm{DGH}_D$ .
2. All maximal elements of $\mathrm{Dom}$ are singletons, ensuring all values in a domain can be generalized to a single common value.
A value generalization hierarchy $\mathrm{VGH}_D$ is a tree rooted at the unique maximal generalized value whose leaves are values of ground domain $D$ , where each value $v \in D_i$ has a unique parent $v' \in D_j$ representing its direct generalization with $D_i \le_D D_j$ .

For a quasi-identifier on ground domain tuple $DT = \langle D_1, \dots, D_n \rangle$ , the domain generalization hierarchy $\mathrm{DGH}_{DT} = \mathrm{DGH}_{D_1} \times \dots \times \mathrm{DGH}_{D_n}$ defines a lattice under coordinate-wise ordering. Each maximal path from $DT$ to the maximal domain tuple forms a generalization strategy.
Knowl 3 — Generalized Tables and Distance Vectors with Tuple Suppression
definition
Let $T_i(A_1, \dots, A_n)$ and $T_j(A_1, \dots, A_n)$ be tables defined on the same attributes. $T_j$ is a generalization of $T_i$ with suppression, denoted $T_i \preceq T_j$ , if and only if:
1. $|T_j| \le |T_i|$ ;
2. $\forall A_z \in \{A_1, \dots, A_n\} : \mathrm{dom}(A_z, T_i) \le_D \mathrm{dom}(A_z, T_j)$ ;
3. There exists an injective mapping from $T_j$ to $T_i$ associating each tuple $t_j \in T_j$ with a tuple $t_i \in T_i$ such that $t_i[A_z] \le_V t_j[A_z]$ for all $A_z \in \{A_1, \dots, A_n\}$ .
Tuples in $T_i$ that have no image in $T_j$ are suppressed tuples. The distance vector between $T_i$ and $T_j$ is $DV_{i,j} = [d_1, \dots, d_n]$ , where each $d_z$ is the length of the path between $\mathrm{dom}(A_z, T_i)$ and $\mathrm{dom}(A_z, T_j)$ in $\mathrm{DGH}_{\mathrm{dom}(A_z, T_i)}$ . Distance vectors are ordered coordinate-wise: $DV \le DV'$ iff $d_z \le d'_z$ for all $z \in \{1, \dots, n\}$ , and $DV < DV'$ iff $DV \le DV'$ and $DV \neq DV'$ .
Knowl 4 — Minimal Required Suppression and Uniqueness Theorem
theoretical result
Let $T_i$ be a table and $T_j$ a generalization of $T_i$ ( $T_i \preceq T_j$ ) satisfying $k$ -anonymity. $T_j$ enforces minimal required suppression if and only if for all $T_z$ such that $T_i \preceq T_z$ , $DV_{i,z} = DV_{i,j}$ , and $T_z$ satisfies $k$ -anonymity, $|T_j| \ge |T_z|$ .

For any table $T_i(A_1, \dots, A_n)$ , distance vector $DV = [d_1, \dots, d_n]$ where $0 \le d_z \le h_z$ ( $h_z$ being the height of $\mathrm{DGH}_{\mathrm{dom}(A_z, T_i)}$ ), and integer $k$ with $0 < k \le |T_i|$ :
1. There exists exactly one generalized table $T_j$ ( $T_i \preceq T_j, DV_{i,j} = DV$ ) satisfying $k$ -anonymity by enforcing minimal required suppression.
2. For any other table $T_z$ ( $T_i \preceq T_z, DV_{i,z} = DV$ ) satisfying $k$ -anonymity, $T_z \neq T_j \implies T_j \supset T_z$ .
This unique table $T_j$ is obtained by generalizing all attribute values in $T_i$ according to distance vector $DV$ and removing all and only tuples whose resulting quasi-identifier value sequence appears with fewer than $k$ occurrences.
Knowl 5 — k-Minimal Generalization with Suppression
definition
Let $T_i$ and $T_j$ be tables such that $T_i \preceq T_j$ , and let $\mathrm{MaxSup} \ge 0$ be a specified integer threshold representing the maximum allowed number of suppressed tuples. The table $T_j$ is a $k$ -minimal generalization of $T_i$ with suppression threshold $\mathrm{MaxSup}$ if and only if:
1. $T_j$ satisfies $k$ -anonymity enforcing minimal required suppression;
2. $|T_i| - |T_j| \le \mathrm{MaxSup}$ ;
3. $\forall T_z : (T_i \preceq T_z \wedge T_z \text{ satisfies (1) and (2)}) \implies \neg(DV_{i,z} < DV_{i,j})$ .
Under this definition, suppression is preferred over generalization up to $\mathrm{MaxSup}$ suppressed tuples, and a generalization is minimal if no other valid generalization exists with a strictly smaller distance vector.
Knowl 6 — Monotonicity of Suppression over the Generalization Lattice
theoretical result
Let $T_i = PT[QI]$ be a private table and let $T_j$ and $T_z$ be two generalizations of $T_i$ ( $T_i \preceq T_j$ and $T_i \preceq T_z$ ) enforcing minimal required suppression for a given $k$ -anonymity requirement.

If $DV_{i,j} < DV_{i,z}$ , then $|T_j| \le |T_z|$ . Consequently, the number of suppressed tuples satisfies:

$|T_i| - |T_z| \le |T_i| - |T_j|$

As a direct corollary, for any suppression threshold $\mathrm{MaxSup}$ :
- If $|T_i| - |T_j| \le \mathrm{MaxSup}$ , then $|T_i| - |T_z| \le \mathrm{MaxSup}$ .
- If $|T_i| - |T_z| > \mathrm{MaxSup}$ , then $|T_i| - |T_j| > \mathrm{MaxSup}$ .
Thus, required suppression monotonically decreases (or stays equal) as generalization increases along any path in the generalization lattice.
Knowl 7 — Lattice-Height Binary Search Algorithm for k-Minimal Generalization
algorithm
The algorithm Find_vector computes a distance vector sol corresponding to a $k$ -minimal generalization of $T_i = PT[QI]$ by conducting a binary search over the height of distance vectors in the lattice $\mathrm{VL}_{DT}$ . The height of a distance vector $DV = [d_1, \dots, d_n]$ is defined as $\mathrm{height}(DV, \mathrm{VL}_{DT}) = \sum_{z=1}^n d_z$ . By monotonicity of suppression, if no vector at height $h$ satisfies $k$ -anonymity with $\le \mathrm{MaxSup}$ suppressed tuples, no solution can exist at any height below $h$ .
Input: Table $T_i = PT[QI]$ , anonymity requirement $k$ , suppression threshold $\mathrm{MaxSup}$ , lattice $\mathrm{VL}_{DT}$
Output: Distance vector $\mathrm{sol}$ of a $k$ -minimal generalization
low := 0
high := height( $\top$ , $\mathrm{VL}_{DT}$ )
sol := $\top$
while low < high do
    try := floor((low + high) / 2)
    Vectors := {vec | height(vec, $\mathrm{VL}_{DT}$ ) = try}
    reach_k := false
    while Vectors != empty and reach_k == false do
        Select and remove a vector vec from Vectors
        if satisfies(vec, k, $T_i$ , $\mathrm{MaxSup}$ ) then
            sol := vec
            reach_k := true
    if reach_k == true then
        high := try
    else
        low := try + 1
return sol
The function satisfies(vec, k, Ti, MaxSup) returns true if the unique generalization of $T_i$ at distance vector vec enforcing minimal required suppression suppresses at most $\mathrm{MaxSup}$ tuples, and false otherwise.
Knowl 8 — Tuple-Level Distance Matrix for Anonymity Evaluation
model/method
The satisfaction check satisfies(vec, k, Ti, MaxSup) can be computed directly without materializing the generalized table by constructing a tuple distance matrix $VT$ .

For any two tuples $x = \langle v'_1, \dots, v'_n \rangle$ and $y = \langle v''_1, \dots, v''_n \rangle$ in $T_i = PT[QI]$ , their distance vector is $V_{x,y} = [d_1, \dots, d_n]$ , where each $d_z$ is the length of the path from the domain of $v'_z$ (and $v''_z$ ) to the lowest common ancestor of $v'_z$ and $v''_z$ in $\mathrm{VGH}_{D_z}$ .
1. Let outliers in $T_i$ be distinct tuples $x$ with occurrence count $\mathrm{count}(x, T_i) < k$ .
2. Matrix $VT$ has a row for each distinct outlier $x$ and a column for each distinct tuple $y \in T_i$ , with entry $VT[x,y] = V_{x,y}$ .
3. For candidate distance vector vec, compute the cluster size for each outlier row $x$ :
$C_x = \sum_{y \in T_i : VT[x,y] \le vec} \mathrm{count}(y, T_i)$
1. Compute total required suppression:
$\mathrm{req\_sup} = \sum_{x : C_x < k} \mathrm{count}(x, T_i)$

The predicate satisfies(vec, k, Ti, MaxSup) evaluates to true if and only if $\mathrm{req\_sup} \le \mathrm{MaxSup}$ .
Knowl 9 — Preference Policies and Data Quality Metrics for Minimal Generalizations
model/method
When multiple $k$ -minimal generalizations exist for a table $T_i$ with distance vector $DV_{i,j} = [d_1, \dots, d_n]$ and domain hierarchy heights $h_z = \mathrm{height}(\mathrm{DGH}_{\mathrm{dom}(A_z, T_i)})$ , preference policies select among them:
- Minimum Absolute Distance: Prefers generalizations minimizing total generalization steps: $\mathrm{Absdist}_{i,j} = \sum_{z=1}^n d_z$
- Minimum Relative Distance: Prefers generalizations minimizing normalized generalization steps: $\mathrm{Reldist}_{i,j} = \sum_{z=1}^n \frac{d_z}{h_z}$
- Maximum Distribution: Prefers generalizations maximizing the number of distinct tuples in the released table.
- Minimum Suppression: Prefers generalizations maximizing output table cardinality $|T_j|$ .
Data quality trade-offs are quantified by:
- Accuracy: $1 - \frac{1}{n} \sum_{z=1}^n \frac{d_z}{h_z}$ (loss of precision via generalization).
- Completeness: $\frac{|T_j|}{|T_i|}$ (loss of data via suppression).

Coverage note — Specific comparison examples with previous heuristic systems (mu-Argus and Datafly) were omitted as they serve as empirical/qualitative contrast rather than primary theoretical contributions of the proposed model.

References

1.N.R. Adam and J.C. Wortman. Security-control methods for statistical databases: A comparative study. ACM Computing Surveys, 21(4):515–556, 1989.
2.Ross Anderson. A security policy model for clinical information systems. In Proc. of the 1996 IEEE Symposium on Security and Privacy, pages 30–43, Oakland, CA, May 1996.
3.L.H. Cox. Suppression methodology and statistical disclosure analysis. Journal of the American Statistical Association, 75:377–385, 1980.
4.Tore Dalenius. Finding a needle in a haystack - or identifying anonymous census record. Journal of Official Statistics, 2(3):329–336, 1986.
5.B.A. Davey and H.A. Priestley. Introduction to Lattices and Order. Cambridge University Press, 1990.
6.Dorothy E. Denning. Cryptography and Data Security. Addison-Wesley, 1982.
7.John Dobson, Sushil Jajodia, Martin Olivier, Pierangela Samarati, and Bhavani Thuraisingham. Privacy issues in www and data mining. IFIP WG11.3 Working Conference on Database Security - Panel Notes, 1998.
8.George T. Duncan, Thomas B. Jabine, and Virginia A. de Wolf, editors. Private Lives and Public Policies. National Academy Press, 1993.
9.A. Hundepool and L. Willenborg. $\mu$ - and $\tau$ -Argus: Software for statistical disclosure control. In Third International Seminar on Statistical Confidentiality, Bled, 1996.
10.Sushil Jajodia and Catherine Meadows. Inference Problems in Multilevel Secure Database Management Systems. In Marshall D. Abrams, Sushil Jajodia, and Harold J. Podell, editors, Information Security - An Integrated Collection of Essays, pages 570–584. IEEE Computer Society Press, 1995.
11.Teresa Lunt. Aggregation and inference: Facts and fallacies. In Proc. of the IEEE Symposium on Security and Privacy, pages 102–109, Oakland, CA, May 1989.
12.Committee on Maintaining Privacy and Security in Health Care Application of the National Information Infrastructure. For the record - protecting electronic health information, 1997.
13.Federal Committee on Statistical Methodology. Statistical policy working paper 22. Report on Statistical Disclosure Limitation Methodology, May 1994.
14.X. Qian, M.E. Stickel, P.D. Karp, T.F. Lunt, and T.D. Garvey. Detection and elimination of inference channels in multilevel relational database systems. In Proc. of the IEEE Symposium on Security and Privacy, pages 196–205, Oakland, CA, May 1993.
15.P. Samarati and L. Sweeney. Protecting privacy when disclosing information: $k$ -anonymity and its enforcement through generalization and suppression. Technical report, SRI International, March 1998.
16.Latanya Sweeney. Guaranteeing anonymity when sharing medical data, the Datafly system. In Proc. Journal of the American Medical Informatics Association, Washington, DC: Hanley & Belfus, Inc., 1997.
17.Latanya Sweeney. Weaving technology and policy together to maintain confidentiality. Journal of Law, Medicine & Ethics, 25(2–3):98–110, 1997.
18.Rein Turn. Information privacy issues for the 1990s. In Proc. of the IEEE Symposium on Security and Privacy, pages 394–400, Oakland, CA, May 1990.
19.Jeffrey D. Ullman. Principles of Databases and Knowledge-Base Systems, volume I. Computer Science Press, 1989.
20.L. Willenborg and T. De Waal. Statistical Disclosure Control in Practice. Springer-Verlag, 1996.
21.Beverly Woodward. The computer-based patient record confidentiality. The New England Journal of Medicine, 333(21):1419–1422, 1995.

Citation

MLA

Samarati, P. “Protecting Respondents Identities in Microdata Release”. IEEE Transactions on Knowledge and Data Engineering, vol. 13, no. 6, 2001, pp. 1010–27, https://doi.org/10.1109/69.971193.

APA

Samarati, P. (2001). Protecting respondents identities in microdata release. IEEE Transactions on Knowledge and Data Engineering, 13(6), 1010–1027. https://doi.org/10.1109/69.971193

Chicago

Samarati, P. 2001. “Protecting Respondents Identities in Microdata Release”. IEEE Transactions on Knowledge and Data Engineering 13 (6): 1010–27. https://doi.org/10.1109/69.971193.

Harvard

Samarati, P. (2001) “Protecting respondents identities in microdata release”, IEEE Transactions on Knowledge and Data Engineering, 13(6), pp. 1010–1027. Available at: https://doi.org/10.1109/69.971193.

Vancouver

1. Samarati P (2001) Protecting respondents identities in microdata release. IEEE Transactions on Knowledge and Data Engineering 13:1010–1027

BibTeX

@article{Samarati_2001, title={Protecting respondents identities in microdata release}, volume={13}, ISSN={1041-4347}, url={http://dx.doi.org/10.1109/69.971193}, DOI={10.1109/69.971193}, number={6}, journal={IEEE Transactions on Knowledge and Data Engineering}, publisher={Institute of Electrical and Electronics Engineers (IEEE)}, author={Samarati, P.}, year={2001}, pages={1010–1027} }

Metadata:Crossref

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

Protecting Respondents' Identities in Microdata Release

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Definition of k-Anonymity and Quasi-Identifiers

Knowl 2 — Domain and Value Generalization Hierarchies and Domain Tuple Lattice

Knowl 3 — Generalized Tables and Distance Vectors with Tuple Suppression

Knowl 4 — Minimal Required Suppression and Uniqueness Theorem

Knowl 5 — k-Minimal Generalization with Suppression

Knowl 6 — Monotonicity of Suppression over the Generalization Lattice

Knowl 7 — Lattice-Height Binary Search Algorithm for k-Minimal Generalization

Knowl 8 — Tuple-Level Distance Matrix for Anonymity Evaluation

Knowl 9 — Preference Policies and Data Quality Metrics for Minimal Generalizations

References

Citation

BibTeX

Access the Paper