Abstract
When a table containing individual data is published, disclosure of sensitive information should be prohibitive. (ε, m)-anonymity was a new anonymization principle for preservation of proximity privacy, in publishing numerical sensitive data. It is shown to be NP-Hard to (ε, m)-anonymize a table minimizing the number of suppressed cells. Extensive performance study verified our findings that our algorithm is significantly better than the traditional algorithms presented in the paper[1].
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Li, J., Tao, Y., Xiao, X.: Preservation of Proximity Privacy in Publishing Numerical Sensitive Data. In: ACM SIGMOD 2008, Vancouver, BC, Canada (2008)
Sweeney, L.: k-anonymity: a model for protecting privacy. International Journal on Uncertainty, Fuzziness, and Knowlege-Based Systems 10(5), 557–570 (2002)
Samarati, P., Sweeney, L.: Generalizing data to provide anonymity when disclosing information. In: Proceedings of the 17th ACM Symposium on the Principle of Database Systems, Seattle, WA (June 1998)
Samarati, P.: Protecting respondents identities in microdata release. IEEE Transactions on Knowledge and Data Engineering 13(6), 1010–1027 (2001)
Bayardo, R., Agrawal, R.: Data privacy through optimal k-anonymization. In: Proc. of International Conference on Data Engineering (ICDE), pp. 217–228 (2005)
Xu, J., Wang, W., Pei, J., Wang, X., Shi, B., Fu, A.W.-C.: Utility-based anonymization using local recoding. In: SIGKDD, pp. 785–790 (2006)
Fung, B.C.M., Wang, K., Yu, P.S.: Top-down specialization for information and privacy preservation. In: ICDE, pp. 205–216 (2005)
LeFevre, K., DeWitt, D.J., Ramakrishnan, R.: Incognito: Efficient full-domain k-anonymity. In: Proc. of ACM Management of Data (SIGMOD), pp. 49–60 (2005)
LeFevre, K., DeWitt, D.J., Ramakrishnan, R.: Mondrian multidimensional k-anonymity. In: Proc. of International Conference on Data Engineering (ICDE), pp. 277–286 (2006)
Machanavajjhala, A., Gehrke, J., Kifer, D., Venkitasubramaniam, M.: L-diversity: Privacy beyond k-anonymity. In: ICDE, pp. 1–24 (2006)
Li, N., Li, T., Venkatasubramanian, S.: t-closeness: Privacy beyond k-anonymity and l-diversity. In: ICDE, pp. 106–115 (2007)
Meyerson, A., Williams, R.: On the complexity of optimal k-anonymity. In: PODS, pp. 223–228 (2004)
Xiao, X.K., Ke, Y., Tao, Y.F.: The Hardness and Approximation Algorithms for L-Diversity. In: EDBT 2010 (2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Li, Y., Li, D., He, X., Wang, W., Chen, H. (2013). The Hardness of (ε, m)-anonymity. In: Wang, J., Xiong, H., Ishikawa, Y., Xu, J., Zhou, J. (eds) Web-Age Information Management. WAIM 2013. Lecture Notes in Computer Science, vol 7923. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-38562-9_75
Download citation
DOI: https://doi.org/10.1007/978-3-642-38562-9_75
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-38561-2
Online ISBN: 978-3-642-38562-9
eBook Packages: Computer ScienceComputer Science (R0)