{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:34:15Z","timestamp":1760243655929,"version":"build-2065373602"},"reference-count":41,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2013,10,17]],"date-time":"2013-10-17T00:00:00Z","timestamp":1381968000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>We suggest a user-oriented approach to combinatorial data anonymization. A data matrix is called k-anonymous if every row appears at least k times\u2014the goal of the NP-hard k-ANONYMITY problem then is to make a given matrix k-anonymous by suppressing (blanking out) as few entries as possible. Building on previous work and coping with corresponding deficiencies, we describe an enhanced k-anonymization problem called PATTERN-GUIDED k-ANONYMITY, where the users specify in which combinations suppressions may occur. In this way, the user of the anonymized data can express the differing importance of various data features. We show that PATTERN-GUIDED k-ANONYMITY is NP-hard. We complement this by a fixed-parameter tractability result based on a \u201cdata-driven parameterization\u201d and, based on this, develop an exact integer linear program (ILP)-based solution method, as well as a simple, but very effective, greedy heuristic. Experiments on several real-world datasets show that our heuristic easily matches up to the established \u201cMondrian\u201d algorithm for k-ANONYMITY in terms of the quality of the anonymization and outperforms it in terms of running time.<\/jats:p>","DOI":"10.3390\/a6040678","type":"journal-article","created":{"date-parts":[[2013,10,17]],"date-time":"2013-10-17T13:39:40Z","timestamp":1382017180000},"page":"678-701","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Pattern-Guided k-Anonymity"],"prefix":"10.3390","volume":"6","author":[{"given":"Robert","family":"Bredereck","sequence":"first","affiliation":[{"name":"Institut f\u00fcr Softwaretechnik und Theoretische Informatik, TU Berlin, Berlin, 10587, Germany"}]},{"given":"Andr\u00e9","family":"Nichterlein","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Softwaretechnik und Theoretische Informatik, TU Berlin, Berlin, 10587, Germany"}]},{"given":"Rolf","family":"Niedermeier","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Softwaretechnik und Theoretische Informatik, TU Berlin, Berlin, 10587, Germany"}]}],"member":"1968","published-online":{"date-parts":[[2013,10,17]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"14:1","DOI":"10.1145\/1749603.1749605","article-title":"Privacy-preserving data publishing: A survey of recent developments","volume":"42","author":"Fung","year":"2010","journal-title":"ACM Comput. Surv."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"476","DOI":"10.1016\/j.ipm.2011.01.004","article-title":"User k-anonymity for privacy preserving data mining of query logs","volume":"48","author":"Torra","year":"2012","journal-title":"Inf. Process. Manag."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1145\/1866739.1866758","article-title":"A firm foundation for private data analysis","volume":"54","author":"Dwork","year":"2011","journal-title":"Commun. ACM"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/s10878-009-9277-y","article-title":"Anonymizing binary and small tables is hard to approximate","volume":"22","author":"Bonizzoni","year":"2011","journal-title":"J. Comb. Optim."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1007\/s10878-011-9428-9","article-title":"Parameterized complexity of k-anonymity: Hardness and tractability","volume":"26","author":"Bonizzoni","year":"2013","journal-title":"J. Comb. Optim."},{"key":"ref_6","unstructured":"Chakaravarthy, V.T., Pandit, V., and Sabharwal, Y. (2010). On the complexity of the k-anonymization problem, arXiv:1004.4729."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1007\/978-3-642-14162-1_33","article-title":"Resolving the Complexity of Some Data Privacy Problems","volume":"Volume 6199","author":"Blocki","year":"2010","journal-title":"Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP \u201910)"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Meyerson, A., and Williams, R. (2004, January 14\u201316). On the Complexity of Optimal k-Anonymity. Proceedings of the 23rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS \u201904), Paris, France.","DOI":"10.1145\/1055558.1055591"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1007\/978-3-642-01718-6_4","article-title":"Data and Structural k-Anonymity in Social Networks","volume":"Volume 5456","author":"Campan","year":"2009","journal-title":"Proceedings of the 2nd ACM SIGKDD International Workshop on Privacy, Security, and Trust in KDD (PinKDD \u201908)"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1145\/1882471.1882473","article-title":"Providing k-Anonymity in location based services","volume":"12","author":"Kalnis","year":"2010","journal-title":"ACM SIGKDD Explor. Newslett."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Loukides, G., and Shao, J. (2007, January 11\u201315). Capturing Data Usefulness and Privacy Protection in k-Anonymisation. Proceedings of the 2007 ACM Symposium on Applied Computing, Seoul, Korea.","DOI":"10.1145\/1244002.1244091"},{"key":"ref_12","unstructured":"Rastogi, V., Suciu, D., and Hong, S. (2007, January 23\u201327). The Boundary between Privacy and Utility in Data Publishing. Proceedings of the 33rd International Conference on Very Large Data Bases, VLDB Endowment, Vienna, Austria."},{"key":"ref_13","first-page":"182","article-title":"Pattern-Guided Data Anonymization and Clustering","volume":"Volume 6907","author":"Bredereck","year":"2011","journal-title":"Proceedings of the 36th International Symposium on Mathematical Foundations of Computer Science (MFCS \u201911)"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Bredereck, R., K\u00f6hler, T., Nichterlein, A., Niedermeier, R., and Philip, G. (2013). Using patterns to form homogeneous teams. Algorithmica.","DOI":"10.1007\/s00453-013-9821-0"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"1010","DOI":"10.1109\/69.971193","article-title":"Protecting respondents identities in microdata release","volume":"13","author":"Samarati","year":"2001","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Samarati, P., and Sweeney, L. (1998, January 1\u20133). Generalizing Data to Provide Anonymity When Disclosing Information. Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS \u201998), Seattle, WA, USA.","DOI":"10.1145\/275487.275508"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"557","DOI":"10.1142\/S0218488502001648","article-title":"k-anonymity: A model for protecting privacy","volume":"10","author":"Sweeney","year":"2002","journal-title":"Int. J. Uncertain. Fuzziness Knowl.-Based Syst."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Downey, R.G., and Fellows, M.R. (1999). Parameterized Complexity, Springer.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"ref_19","unstructured":"Flum, J., and Grohe, M. (2006). Parameterized Complexity Theory, Springer."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Niedermeier, R. (2006). Invitation to Fixed-Parameter Algorithms, Oxford University Press.","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"LeFevre, K., DeWitt, D., and Ramakrishnan, R. (2006, January 3\u20137). Mondrian Multidimensional k-anonymity. Proceedings of the IEEE 22nd International Conference on Data Engineering (ICDE \u201906), Atlanta, GA, USA.","DOI":"10.1109\/ICDE.2006.101"},{"key":"ref_22","unstructured":"Frank, A., and Asuncion, A. UCI Machine Learning Repository, University of California, Irvine, School of Information and Computer Sciences. http:\/\/archive.ics.uci.edu\/ml."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Machanavajjhala, A., Kifer, D., Gehrke, J., and Venkitasubramaniam, M. (2007). \u2113-diversity: Privacy beyond k-anonymity. ACM Trans. Knowl. Discov. Data, 1.","DOI":"10.1145\/1217299.1217302"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1007\/s10878-009-9253-6","article-title":"Fixed-parameter tractability of anonymizing data by suppressing entries","volume":"18","author":"Evans","year":"2009","journal-title":"J. Comb. Optim."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Miller, R.E., and Thatcher, J.W. (1972). Complexity of Computer Computations, Plenum Press.","DOI":"10.1007\/978-1-4684-2001-2"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"678","DOI":"10.1137\/090752699","article-title":"Terminal backup, 3D matching, and covering cubic graphs","volume":"40","author":"Anshelevich","year":"2011","journal-title":"SIAM J. Comput."},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Bredereck, R., Nichterlein, A., Niedermeier, R., and Philip, G. (2012). The effect of homogeneity on the computational complexity of combinatorial data anonymization. Data Min. Knowl. Discov.","DOI":"10.1007\/s10618-012-0293-7"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"490","DOI":"10.1145\/367390.367400","article-title":"Trie memory","volume":"3","author":"Fredkin","year":"1960","journal-title":"Commun. ACM"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1287\/moor.8.4.538","article-title":"Integer programming with a fixed number of variables","volume":"8","author":"Lenstra","year":"1983","journal-title":"Math. Oper. Res."},{"key":"ref_30","unstructured":"Adult dataset. Available online: ftp:\/\/ftp.ics.uci.edu\/pub\/machine-learning-databases\/adult\/."},{"key":"ref_31","unstructured":"Nursery dataset. Available online: ftp:\/\/ftp.ics.uci.edu\/pub\/machine-learning-databases\/nursery\/."},{"key":"ref_32","first-page":"145","article-title":"An application for admission in public school systems","volume":"145","author":"Olave","year":"1989","journal-title":"Expert Syst. Public Adm."},{"key":"ref_33","unstructured":"CMC dataset. Available online: ftp:\/\/ftp.ics.uci.edu\/pub\/machine-learning-databases\/cmc\/."},{"key":"ref_34","unstructured":"Canada dataset. Available online: http:\/\/www.hc-sc.gc.ca\/dhp-mps\/medeff\/databasdon\/index-eng.php."},{"key":"ref_35","unstructured":"Canada attribute names. Available online: http:\/\/www.hc-sc.gc.ca\/dhp-mps\/medeff\/databasdon\/structure-eng.php#a1."},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Mainland, G., Leshchinskiy, R., and Peyton Jones, S. (2013, January 25\u201327). Exploiting Vector Instructions with Generalized Stream Fusion. Proceedings of the 18th ACM SIGPLAN International Conference on Functional Programming (ICFP \u201913), Boston, MA, USA.","DOI":"10.1145\/2500365.2500601"},{"key":"ref_37","unstructured":"Pattern-Guided k-Anonymity heuristic. Available online: http:\/\/akt.tu-berlin.de\/menue\/software\/."},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Li, N., Li, T., and Venkatasubramanian, S. (2007, January 15\u201320). t-Closeness: Privacy Beyond k-Anonymity and l-Diversity. Proceedings of the IEEE 23rd International Conference on Data Engineering (ICDE \u201907), Istanbul, Turkey.","DOI":"10.1109\/ICDE.2007.367856"},{"key":"ref_39","unstructured":"Mondrian implementation. Available online: http:\/\/cs.utdallas.edu\/dspl\/cgi-bin\/toolbox\/."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"571","DOI":"10.1142\/S021848850200165X","article-title":"Achieving k-anonymity privacy protection using generalization and suppression","volume":"10","author":"Sweeney","year":"2002","journal-title":"Int. J. Uncertain. Fuzziness Knowl.-Based Syst."},{"key":"ref_41","doi-asserted-by":"crossref","unstructured":"Truta, T.M., and Vinay, B. (2006, January 3\u20137). Privacy Protection: p-Sensitive k-Anonymity Property. Proceedings of the 22nd International Conference on Data Engineering Workshops (ICDE \u201906), Atlanta, GA, USA.","DOI":"10.1109\/ICDEW.2006.116"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/6\/4\/678\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T21:49:57Z","timestamp":1760219397000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/6\/4\/678"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,10,17]]},"references-count":41,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2013,12]]}},"alternative-id":["a6040678"],"URL":"https:\/\/doi.org\/10.3390\/a6040678","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2013,10,17]]}}}