research-article

Micro-aggregation-based heuristics for p-sensitive k-anonymity: one step beyond

Authors:

Agusti Solanas,

Francesc Sebé,

Josep Domingo-FerrerAuthors Info & Claims

PAIS '08: Proceedings of the 2008 international workshop on Privacy and anonymity in information society

Pages 61 - 69

https://doi.org/10.1145/1379287.1379300

Published: 29 March 2008 Publication History

Abstract

Micro-data protection is a hot topic in the field of Statistical Disclosure Control (SDC), that has gained special interest after the disclosure of 658000 queries by the AOL search engine in August 2006. Many algorithms, methods and properties have been proposed to deal with micro-data disclosure, p-Sensitive k-anonymity has been recently defined as a sophistication of k-anonymity. This new property requires that there be at least p different values for each confidential attribute within the records sharing a combination of key attributes. Like k-anonymity, the algorithm originally proposed to achieve this property was based on generalisations and suppressions; when data sets are numerical this has several data utility problems, namely turning numerical key attributes into categorical, injecting new categories, injecting missing data, and so on. In this article, we recall the foundational concepts of micro-aggregation, k-anonymity and p-sensitive k-anonymity. We show that k-anonymity and p-sensitive k-anonymity can be achieved in numerical data sets by means of micro-aggregation heuristics properly adapted to deal with this task. In addition, we present and evaluate two heuristics for p-sensitive k-anonymity which, being based on micro-aggregation, overcome most of the drawbacks resulting from the generalisation and suppression method.

References

[1]

G. Aggarwal, T. Feder, K. Kenthapadi, R. Motwani, R. Panigrahy, D. Thomas, and A. Zhu. k-anonymity: Algorithms and hardness. Technical report, Stanford University, 2004.

[2]

C. Boyens, R. Krishnan, and R. Padman. On privacy-preserving access to distributed heterogeneous healthcare information. In I. C. Society, editor, Proceedings of the 37th Hawaii International Conference on System Sciences HICSS-37, Big Island, HI., 2004.

Digital Library

[3]

A. Campan, T. M. Truta, J. Miller, and R. Sinca. A clustering approach for achieving data privacy. In R. Stahlbock, S. F. Crone, and S. Lessmann, editors, DMIN, pages 321--330. CSREA Press, 2007.

[4]

T. Dalenius. Finding a needle in a haystack - or identifying anonymous census records. Journal of Official Statistics, 2(3):329--336, 1986.

[5]

J. Domingo-Ferrer and J. M. Mateo-Sanz. Practical data-oriented microaggregation for statistical disclosure control. IEEE Transactions on Knowledge and Data Engineering, 14(1):189--201, 2002.

Digital Library

[6]

J. Domingo-Ferrer and V. Torra. A critique of the sensitivity rules usually employed for statistical table protection. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 10(5):545--556, 2002.

Digital Library

[7]

J. Domingo-Ferrer and V. Torra. Ordinal, continuous and heterogenerous k-anonymity through microaggregation. Data Mining and Knowledge Discovery, 11(2):195--212, 2005.

Digital Library

[8]

HIPAA. Health insurance portability and accountability act, 2004. http://www.hhs.gov/ocr/hipaa/.

[9]

A. Hundepool, J. Domingo-Ferrer, L. Franconi, S. Giessing, R. Lenz, J. Longhurst, E. Schulte-Nordholt, G. Seri, and P.-P. DeWolf. Handbook on Statistical Disclosure Control (version 1.0). Eurostat (CENEX SDC Project Deliverable), 2006.

[10]

K. LeFevre, D. J. DeWitt, and R. Ramakrishnan. Incognito: Efficient full-domain k-anonymity. In F. &Ecaron;zcan, editor, SIGMOD Conference, pages 49--60. ACM, 2005.

Digital Library

[11]

A. Meyerson and R. Williams. On the complexity of optimal k-anonymity. In Proc. of the ACM Symposium on Principles of Database Systems-PODS '2004, pages 223--228, Paris, France, 2004. ACM.

Digital Library

[12]

A. Oganian and J. Domingo-Ferrer. On the complexity of optimal microaggregation for statistical disclosure control. Statistical Journal of the United Nations Economic Comission for Europe, 18(4):345--354, 2001.

[13]

E. Parliament. DIRECTIVE 2002/58/EC of the European Parliament and Council of 12 July 2002 concerning the processing of personal data and the protection of privacy in the electronic communications sector (Directive on privacy and electronic communications), 2002. http://europa.eu.int/eur-lex/pri/en/oj/dat/2002/1_201/1_20120020731en00370047.pdf.

[14]

C. Privacy. Canadian privacy regulations, 2005. http://www.media-awareness.ca/english/issues/privacy/canadian_legislation_privacy.cfm.

[15]

P. Samarati. Protecting respondents' identities in microdata release. IEEE Transactions on Knowledge and Data Engineering, 13(6):1010--1027, 2001.

Digital Library

[16]

P. Samarati and L. Sweeney. Protecting privacy when disclosing information: k-anonymity and its enforcement through generalization and suppression. Technical report, SRI International, 1998.

[17]

A. Solanas, J. Domingo-Ferrer, A. Martinez-Balleste, and V. Daza. A Distributed Architecture for Scalable RFID Identification. Computer Networks, 51, 2007.

Digital Library

[18]

A. Solanas and A. Martinez-Balleste. Privacy protection in location-based services through a public-key privacy homomorphism. In J. Lopez, P. Samarati, and J. Ferrer, editors, 4th European PKI Workshop. EuroPKI '07, volume 4582, pages 362 -368. Springer, June 2007.

Digital Library

[19]

L. Sweeney. Achieving k-anonymity privacy protection using generalization and suppression. International Journal of Uncertainty, Fuzziness and Knowledge Based Systems, 10(5):571--588, 2002.

Digital Library

[20]

L. Sweeney, k-anonimity: A model for protecting privacy. International Journal of Uncertainty, Fuzziness and Knowledge Based Systems, 10(5):557--570, 2002.

Digital Library

[21]

T. M. Truta, A. Campan, and P. Meyer. Generating microdata with p-sensitive k-anonymity. In Secure Data Management-4th VLDB Workshop SDM '2007, volume 4721 of Lecture Notes in Computer Science, pages 124--141, Berlin Heidelberg, 2007.

Digital Library

[22]

T. M. Truta and B. Vinay. Privacy protection: p-sensitive k-anonymity property. In 2nd International Workshop on Privacy Data Management PDM 2006, page p. 94, Berlin Heidelberg, 2006. IEEE Computer Society.

Digital Library

[23]

USPrivacy. U.S. privacy regulations, 2005. http://www.media-awareness.ca/english/issues/privacy/us_legislation_privacy.cfm.

Cited By

Khatir RIzadkhah HRazmara J(2023)Designing a Novel Approach Using a Greedy and Information-Theoretic Clustering-Based Algorithm for Anonymizing Microdata SetsEntropy10.3390/e2512161325:12(1613)Online publication date: 1-Dec-2023
https://doi.org/10.3390/e25121613
Oprescu AMisdorp Svan Elsen K(2022)Energy cost and accuracy impact of k-anonymity2022 International Conference on ICT for Sustainability (ICT4S)10.1109/ICT4S55073.2022.00018(65-76)Online publication date: Jun-2022
https://doi.org/10.1109/ICT4S55073.2022.00018
Harn PYeddula SSun LSun MKu W(2022)Location-based Alert System Using Searchable Encryption with Hilbert Curve Encoding2022 IEEE International Conference on Big Data (Big Data)10.1109/BigData55660.2022.10020428(1445-1454)Online publication date: 17-Dec-2022
https://doi.org/10.1109/BigData55660.2022.10020428
Show More Cited By

Index Terms

Micro-aggregation-based heuristics for p-sensitive k-anonymity: one step beyond

Recommendations

Generating microdata with p-sensitive k-anonymity property
SDM'07: Proceedings of the 4th VLDB conference on Secure data management

Existing privacy regulations together with large amounts of available data have created a huge interest in data privacy research. A main research direction is built around the k-anonymity property. Several shortcomings of the k-anonymity model have been ...
Personalized sensitive attribute anonymity based on P - sensitive k anonymity
ICIIP '16: Proceedings of the 1st International Conference on Intelligent Information Processing

With the development of science and technology, privacy protection has also been highly valued. Existing anonymity algorithms are only anonymous quasi-identifier to achieve privacy protection, but ignore the sensitive properties of the personalized ...
User-controlled generalization boundaries for p-sensitive k-anonymity
SAC '10: Proceedings of the 2010 ACM Symposium on Applied Computing

Numerous privacy models based on the k-anonymity property have been introduced in the last few years. While differing in their methods and quality of their results, they all focus first on masking the data, and then protecting the quality of the data as ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

PAIS '08: Proceedings of the 2008 international workshop on Privacy and anonymity in information society

March 2008

75 pages

ISBN:9781595939654

DOI:10.1145/1379287

Editors:
Farshad Fotouhi
Wayne State University
,
Li Xiong
Emory University
,
Traian Marius Truta
Northern Kentucky University

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

UNESCO

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 29 March 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Spanish Ministry of Education
Generalitat de Catalunya

Conference

EDBT '08

Sponsor:

EDBT '08: 11th International Conference on Extending Database Technology

March 29, 2008

Nantes, France

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

26
Total Citations
View Citations
347
Total Downloads

Downloads (Last 12 months)11
Downloads (Last 6 weeks)1

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Khatir RIzadkhah HRazmara J(2023)Designing a Novel Approach Using a Greedy and Information-Theoretic Clustering-Based Algorithm for Anonymizing Microdata SetsEntropy10.3390/e2512161325:12(1613)Online publication date: 1-Dec-2023
https://doi.org/10.3390/e25121613
Oprescu AMisdorp Svan Elsen K(2022)Energy cost and accuracy impact of k-anonymity2022 International Conference on ICT for Sustainability (ICT4S)10.1109/ICT4S55073.2022.00018(65-76)Online publication date: Jun-2022
https://doi.org/10.1109/ICT4S55073.2022.00018
Harn PYeddula SSun LSun MKu W(2022)Location-based Alert System Using Searchable Encryption with Hilbert Curve Encoding2022 IEEE International Conference on Big Data (Big Data)10.1109/BigData55660.2022.10020428(1445-1454)Online publication date: 17-Dec-2022
https://doi.org/10.1109/BigData55660.2022.10020428
Mdee ASaad MKhan MKhan MKim D(2022)Impacts of location-privacy preserving schemes on vehicular applicationsVehicular Communications10.1016/j.vehcom.2022.100499(100499)Online publication date: Jun-2022
https://doi.org/10.1016/j.vehcom.2022.100499
Huang PZhang XGuo LLi M(2021)Incentivizing Crowdsensing-Based Noise Monitoring with Differentially-Private LocationsIEEE Transactions on Mobile Computing10.1109/TMC.2019.294680020:2(519-532)Online publication date: 1-Feb-2021
https://doi.org/10.1109/TMC.2019.2946800
Gheisari MPham QAlazab MZhang XFernandez-Campusano CSrivastava G(2019)ECA: An Edge Computing Architecture for Privacy-Preserving in IoT-Based Smart CityIEEE Access10.1109/ACCESS.2019.29371777(155779-155786)Online publication date: 2019
https://doi.org/10.1109/ACCESS.2019.2937177
Li FChen YNiu BHe YGeng KCao J(2018)Achieving Personalized k-Anonymity against Long-Term Observation in Location-Based Services2018 IEEE Global Communications Conference (GLOBECOM)10.1109/GLOCOM.2018.8647719(1-6)Online publication date: Dec-2018
https://doi.org/10.1109/GLOCOM.2018.8647719
Liu BZhou WZhu TGao LXiang Y(2018)Location Privacy and Its Applications: A Systematic StudyIEEE Access10.1109/ACCESS.2018.28222606(17606-17624)Online publication date: 2018
https://doi.org/10.1109/ACCESS.2018.2822260
Chatzikokolakis KElSalamouny EPalamidessi C(2017)Efficient Utility Improvement for Location PrivacyProceedings on Privacy Enhancing Technologies10.1515/popets-2017-00512017:4(308-328)Online publication date: 10-Oct-2017
https://doi.org/10.1515/popets-2017-0051
Tonni SRahman MParvin SGawanmeh A(2017)Securing Big Data Efficiently through Microaggregation Technique2017 IEEE 37th International Conference on Distributed Computing Systems Workshops (ICDCSW)10.1109/ICDCSW.2017.65(125-130)Online publication date: Jun-2017
https://doi.org/10.1109/ICDCSW.2017.65
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents