Approximate Algorithms for k-Anonymity

Summary: Proposes approximation algorithms for k-anonymity in data publishing, addressing linking attacks on quasi-identifiers. Delivers O(log k)-approximation guarantees and O(beta log k)-time variants, outperforming O(k) and O(k log k) baselines; experiments show practical gains. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 3902
Venue: SIGMOD
Year: 2007
Pagerank: 5.8416386e-05
Overall Rank: 6,554 | 55.04%
DOI: 10.1145/1247480.1247490

Incoming Non-self Citations Over Time

Authors

1. Hyoungmin Park (Seoul National University)
2. Kyuseok Shim (Seoul National University)

BibTeX Citation

@inproceedings{park_sigmod07,
        title = {{Approximate Algorithms for k-Anonymity}},
        author = {Park, Hyoungmin and Shim, Kyuseok},
        series = {{SIGMOD} '07},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1247480.1247490},
        url = {https://dl.acm.org/doi/10.1145/1247480.1247490},
        year = {2007}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,232	Privacy-preserving Anonymization of Set-valued Data	2008	VLDB	7.6179491e-05
9,001	Dynamic Anonymization: Accurate Statistical Analysis with Privacy Preservation	2008	SIGMOD	5.334788e-05
9,487	Preservation of Proximity Privacy in Publishing Numerical Sensitive Data	2008	SIGMOD	5.2634238e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
161	Mining Frequent Patterns without Candidate Generation	2000	SIGMOD	0.00027981772
338	Generalizing Data to Provide Anonymity when Disclosing Information	1998	PODS	0.00020731054
384	On the Complexity of Optimal K-Anonymity	2004	PODS	0.00019510305
450	Incognito: Efficient Full-Domain K-Anonymity	2005	SIGMOD	0.00018155142
1,817	On k-Anonymity and the Curse of Dimensionality	2005	VLDB	9.6832973e-05
3,110	Achieving Anonymity via Clustering	2006	PODS	7.7477034e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,424	Non-homogeneous Generalization in Privacy Preserving Data Publishing	2010	SIGMOD
2	11,144	Improved Approximation Algorithms for Relational Clustering	2024	PODS
3	7,875	Privacy-Enhancing k-Anonymization of Customer Data	2005	PODS
4	9,086	Privacy Preservation by Disassociation	2012	VLDB
5	450	Incognito: Efficient Full-Domain K-Anonymity	2005	SIGMOD
6	3,232	Privacy-preserving Anonymization of Set-valued Data	2008	VLDB
7	338	Generalizing Data to Provide Anonymity when Disclosing Information	1998	PODS
8	4,699	Fast Data Anonymization with Low Information Loss	2007	VLDB
9	3,110	Achieving Anonymity via Clustering	2006	PODS
10	384	On the Complexity of Optimal K-Anonymity	2004	PODS