Abstract
The NP-hard k-Anonymity problem asks, given an n ×m-matrix M over a fixed alphabet and an integer s > 0, whether M can be made k-anonymous by suppressing (blanking out) at most s entries. A matrix M is said to be k-anonymous if for each row r in M there are at least k–1 other rows in M which are identical to r. Complementing previous work, we introduce two new “data-driven” parameterizations for k-Anonymity—the number \({t_{\textrm{in}}}\) of different input rows and the number \(t_{\textrm{out}}\) of different output rows—both modeling aspects of data homogeneity. We show that k-Anonymity is fixed-parameter tractable for the parameter \({t_{\textrm{in}}}\), and it is NP-hard even for \({t_{\textrm{out}}} = 2\) and alphabet size four. Notably, our fixed-parameter tractability result implies that k-Anonymity can be solved in linear time when \({t_{\textrm{in}}}\) is a constant. Our results also extend to some interesting generalizations of k-Anonymity.
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
Aggarwal, G., Feder, T., Kenthapadi, K., Khuller, S., Panigrahy, R., Thomas, D., Zhu, A.: Achieving anonymity via clustering. ACM Trans. Algorithms 6(3), 1–19 (2010)
Aggarwal, G., Feder, T., Kenthapadi, K., Motwani, R., Panigrahy, R., Thomas, D., Zhu, A.: Anonymizing tables. In: Eiter, T., Libkin, L. (eds.) ICDT 2005. LNCS, vol. 3363, pp. 246–258. Springer, Heidelberg (2005)
Blocki, J., Williams, R.: Resolving the complexity of some data privacy problems. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol. 6199, pp. 393–404. Springer, Heidelberg (2010)
Bonizzoni, P., DellaVedova, G., Dondi, R.: Anonymizing binary and small tables is hard to approximate. J. Comb. Optim. 22, 97–119 (2011)
Bonizzoni, P., Della Vedova, G., Dondi, R., Pirola, Y.: Parameterized complexity of k-anonymity: Hardness and tractability. In: Iliopoulos, C.S., Smyth, W.F. (eds.) IWOCA 2010. LNCS, vol. 6460, pp. 242–255. Springer, Heidelberg (2011)
Bredereck, R., Nichterlein, A., Niedermeier, R., Philip, G.: Pattern-guided data anonymization and clustering. In: Proc. 36th MFCS. LNCS. Springer, Heidelberg (to appear, 2011)
Chakaravarthy, V.T., Pandit, V., Sabharwal, Y.: On the complexity of the k-anonymization problem. CoRR, abs/1004.4729 (2010)
Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999)
Dwork, C.: A firm foundation for private data analysis. Commun. ACM 54, 86–95 (2011)
Evans, P.A., Wareham, T., Chaytor, R.: Fixed-parameter tractability of anonymizing data by suppressing entries. J. Comb. Optim. 18(4), 362–375 (2009)
Fard, A.M., Wang, K.: An effective clustering approach to web query log anonymization. In: Proc. SECRYPT, pp. 109–119. SciTePress (2010)
Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Heidelberg (2006)
Fredkin, E.: Trie memory. Commun. ACM 3(9), 490–499 (1960)
Fung, B.C.M., Wang, K., Chen, R., Yu, P.S.: Privacy-preserving data publishing: A survey of recent developments. ACM Comput. Surv. 42(4), 14:1–14:53 (2010)
Johnson, D.S.: The NP-completeness column: An ongoing guide. J. Algorithms 8, 438–448 (1987)
Komusiewicz, C., Niedermeier, R., Uhlmann, J.: Deconstructing intractability–A multivariate complexity analysis of interval constrained coloring. J. Discrete Algorithms 9, 137–151 (2011)
Li, N., Li, T., Venkatasubramanian, S.: t-closeness: Privacy beyond k-anonymity and l-diversity. In: Proc. 23rd ICDE, pp. 106–115. IEEE, Los Alamitos (2007)
Machanavajjhala, A., Kifer, D., Gehrke, J., Venkitasubramaniam, M.: ℓ-diversity: Privacy beyond k-anonymity. ACM Trans. Knowl. Discov. Data 1, 52 (2007)
Meyerson, A., Williams, R.: On the complexity of optimal k-anonymity. In: Proc. 23rd PODS, pp. 223–228. ACM, New York (2004)
Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, Oxford (2006)
Niedermeier, R.: Reflections on multivariate algorithmics and problem parameterization. In: Proc. 27th STACS. LIPIcs, vol. 5, pp. 17–32. IBFI, Dagstuhl (2010)
Orlin, J.: A faster strongly polynomial minimum cost flow algorithm. In: Proc. 20th STOC, pp. 377–387. ACM, New York (1988)
Sweeney, L.: Achieving k-anonymity privacy protection using generalization and suppression. IJUFKS 10(5), 571–588 (2002)
Sweeney, L.: k-anonymity: A model for protecting privacy. IJUFKS 10(5), 557–570 (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bredereck, R., Nichterlein, A., Niedermeier, R., Philip, G. (2011). The Effect of Homogeneity on the Complexity of k-Anonymity. In: Owe, O., Steffen, M., Telle, J.A. (eds) Fundamentals of Computation Theory. FCT 2011. Lecture Notes in Computer Science, vol 6914. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-22953-4_5
Download citation
DOI: https://doi.org/10.1007/978-3-642-22953-4_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-22952-7
Online ISBN: 978-3-642-22953-4
eBook Packages: Computer ScienceComputer Science (R0)