Incognito: Efficient Full-Domain K-Anonymity

Summary: Framework for full-domain generalization in k-anonymity; algorithms produce minimal generalizations and are up to 10× faster than prior work. Provides a unified taxonomy of k-anonymization models with new alternatives. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h511d725b1308c4aa
Venue: SIGMOD
Year: 2005
Pagerank: 0.0001775622
Overall Rank: 469 | 96.85%
DOI: 10.1145/1066157.1066164

Incoming Non-self Citations Over Time

Authors

1. Kristen LeFevre (University of Wisconsin)
2. David J. DeWitt (University of Wisconsin)
3. Raghu Ramakrishnan (University of Wisconsin)

BibTeX Citation

@inproceedings{lefevre_sigmod05,
        title = {{Incognito: Efficient Full-Domain K-Anonymity}},
        author = {LeFevre, Kristen and DeWitt, David J. and Ramakrishnan, Raghu},
        series = {{SIGMOD} '05},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1066157.1066164},
        url = {https://dl.acm.org/doi/10.1145/1066157.1066164},
        year = {2005}
}

Incoming Citations (Sorted by Pagerank)

Showing 34 of 34 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
584	Anatomy: Simple and Effective Privacy Preservation	2006	VLDB	0.00015954725
1,020	m-Invariance: Towards Privacy Preserving Re-publication of Dynamic Datasets	2007	SIGMOD	0.00012443542
1,323	Minimality Attack in Privacy Preserving Data Publishing	2007	VLDB	0.00011028542
1,705	Injecting Utility into Anonymized Datasets	2006	SIGMOD	9.831451e-05
1,768	The New Casper: Query Processing for Location Services without Compromising Privacy	2006	VLDB	9.6873901e-05
1,782	The Boundary Between Privacy and Utility in Data Publishing	2007	VLDB	9.652327e-05
2,296	Attacks on Privacy and deFinetti's Theorem	2009	SIGMOD	8.6789249e-05
2,453	Personalized Privacy Preservation	2006	SIGMOD	8.4435151e-05
3,165	Achieving Anonymity via Clustering	2006	PODS	7.5767906e-05
3,293	Privacy-preserving Anonymization of Set-valued Data	2008	VLDB	7.4490004e-05
4,086	Differential Privacy in Telco Big Data Platform	2015	VLDB	6.8150306e-05
4,133	Privacy Skyline: Privacy with Multidimensional Adversarial Knowledge	2007	VLDB	6.7880955e-05
4,430	Anonymization of Set-Valued Data via Top-Down, Local Generalization	2009	VLDB	6.6024228e-05
4,628	Hiding the Presence of Individuals from Shared Databases	2007	SIGMOD	6.4962867e-05
4,794	Optimal Random Perturbation at Multiple Privacy Levels	2009	VLDB	6.4124756e-05
4,802	Fast Data Anonymization with Low Information Loss	2007	VLDB	6.4095862e-05
6,678	Approximate Algorithms for k-Anonymity	2007	SIGMOD	5.710693e-05
7,788	K-Anonymization as Spatial Indexing: Toward Scalable and Incremental Anonymization	2007	VLDB	5.4526034e-05
8,373	SAP HANA goes private – From Privacy Research to Privacy Aware Enterprise Analytics	2019	VLDB	5.3443759e-05
8,715	Privacy Preserving Serial Data Publishing By Role Composition	2008	VLDB	5.2905577e-05
8,826	Privacy-MaxEnt: Integrating Background Knowledge in Privacy Quantification	2008	SIGMOD	5.268646e-05
8,942	Data Publishing against Realistic Adversaries	2009	VLDB	5.2546575e-05
9,164	Dynamic Anonymization: Accurate Statistical Analysis with Privacy Preservation	2008	SIGMOD	5.2151493e-05
9,260	Privacy Preservation by Disassociation	2012	VLDB	5.2056825e-05
9,261	Preserving Privacy and Fairness in Peer-to-Peer Data Integration	2010	SIGMOD	5.2056825e-05
9,666	Minimizing Minimality and Maximizing Utility: Analyzing Method-based attacks on Anonymized Data	2010	VLDB	5.1453267e-05
9,667	Preservation of Proximity Privacy in Publishing Numerical Sensitive Data	2008	SIGMOD	5.1453267e-05
11,989	Practical Security and Privacy for Database Systems	2021	SIGMOD	4.9793485e-05
12,543	Utility-Maximizing Event Stream Suppression	2013	SIGMOD	4.9793485e-05
12,617	Publishing Microdata with a Robust Privacy Guarantee	2012	VLDB	4.9793485e-05
12,715	Non-homogeneous Generalization in Privacy Preserving Data Publishing	2010	SIGMOD	4.9793485e-05
12,798	Interactive Anonymization of Sensitive Data	2009	SIGMOD	4.9793485e-05
12,827	Distribution-based Microdata Anonymization	2009	VLDB	4.9793485e-05
12,835	Publishing Naive Bayesian Classifiers: Privacy without Accuracy Loss	2009	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
11	Implementing Data Cubes Efficiently	1996	SIGMOD	0.00071084324
29	Fast Algorithms for Mining Association Rules	1994	VLDB	0.0005121339
404	On the Complexity of Optimal K-Anonymity	2004	PODS	0.00019081867
475	Mining Generalized Association Rules	1995	VLDB	0.00017672519

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,796	Anonymized Data: Generation, Models, Usage	2009	SIGMOD
2	404	On the Complexity of Optimal K-Anonymity	2004	PODS
3	12,715	Non-homogeneous Generalization in Privacy Preserving Data Publishing	2010	SIGMOD
4	8,041	Privacy-Enhancing k-Anonymization of Customer Data	2005	PODS
5	6,678	Approximate Algorithms for k-Anonymity	2007	SIGMOD
6	9,260	Privacy Preservation by Disassociation	2012	VLDB
7	3,165	Achieving Anonymity via Clustering	2006	PODS
8	3,293	Privacy-preserving Anonymization of Set-valued Data	2008	VLDB
9	4,802	Fast Data Anonymization with Low Information Loss	2007	VLDB
10	347	Generalizing Data to Provide Anonymity when Disclosing Information	1998	PODS