{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,1]],"date-time":"2025-11-01T13:55:13Z","timestamp":1762005313419,"version":"build-2065373602"},"reference-count":33,"publisher":"MDPI AG","issue":"6","license":[{"start":{"date-parts":[[2021,5,21]],"date-time":"2021-05-21T00:00:00Z","timestamp":1621555200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Symmetry"],"abstract":"<jats:p>The collection of personal data is exponentially growing and, as a result, individual privacy is endangered accordingly. With the aim to lessen privacy risks whilst maintaining high degrees of data utility, a variety of techniques have been proposed, being microaggregation a very popular one. Microaggregation is a family of perturbation methods, in which its principle is to aggregate personal data records (i.e., microdata) in groups so as to preserve privacy through k-anonymity. The multivariate microaggregation problem is known to be NP-Hard; however, its univariate version could be optimally solved in polynomial time using the Hansen-Mukherjee (HM) algorithm. In this article, we propose a heuristic solution to the multivariate microaggregation problem inspired by the Traveling Salesman Problem (TSP) and the optimal univariate microaggregation solution. Given a multivariate dataset, first, we apply a TSP-tour construction heuristic to generate a Hamiltonian path through all dataset records. Next, we use the order provided by this Hamiltonian path (i.e., a given permutation of the records) as input to the Hansen-Mukherjee algorithm, virtually transforming it into a multivariate microaggregation solver we call Multivariate Hansen-Mukherjee (MHM). Our intuition is that good solutions to the TSP would yield Hamiltonian paths allowing the Hansen-Mukherjee algorithm to find good solutions to the multivariate microaggregation problem. We have tested our method with well-known benchmark datasets. Moreover, with the aim to show the usefulness of our approach to protecting location privacy, we have tested our solution with real-life trajectories datasets, too. We have compared the results of our algorithm with those of the best performing solutions, and we show that our proposal reduces the information loss resulting from the microaggregation. Overall, results suggest that transforming the multivariate microaggregation problem into its univariate counterpart by ordering microdata records with a proper Hamiltonian path and applying an optimal univariate solution leads to a reduction of the perturbation error whilst keeping the same privacy guarantees.<\/jats:p>","DOI":"10.3390\/sym13060916","type":"journal-article","created":{"date-parts":[[2021,5,21]],"date-time":"2021-05-21T02:13:46Z","timestamp":1621563226000},"page":"916","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Improving Multivariate Microaggregation through Hamiltonian Paths and Optimal Univariate Microaggregation"],"prefix":"10.3390","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6938-583X","authenticated-orcid":false,"given":"Armando","family":"Maya-L\u00f3pez","sequence":"first","affiliation":[{"name":"Department of Computer Engineering and Mathematics, Universitat Rovira i Virgili, Av. Pa\u00efsos Catalans 26, 43007 Tarragona, Catalonia, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4296-2876","authenticated-orcid":false,"given":"Fran","family":"Casino","sequence":"additional","affiliation":[{"name":"Department of Informatics, University of Piraeus, Karaoli kai dimitriou 80, 18534 Pireas, Greece"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4881-6215","authenticated-orcid":false,"given":"Agusti","family":"Solanas","sequence":"additional","affiliation":[{"name":"Department of Computer Engineering and Mathematics, Universitat Rovira i Virgili, Av. Pa\u00efsos Catalans 26, 43007 Tarragona, Catalonia, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2021,5,21]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Ye, H., Cheng, X., Yuan, M., Xu, L., Gao, J., and Cheng, C. (2016, January 26\u201328). A survey of security and privacy in big data. Proceedings of the 2016 16th International Symposium on Communications and Information Technologies (ISCIT), Qingdao, China.","DOI":"10.1109\/ISCIT.2016.7751634"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Vatsalan, D., Sehili, Z., Christen, P., and Rahm, E. (2017). Privacy-Preserving Record Linkage for Big Data: Current Approaches and Research Challenges. Handbook of Big Data Technologies, Springer International Publishing.","DOI":"10.1007\/978-3-319-49340-4_25"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"1821","DOI":"10.1109\/ACCESS.2016.2558446","article-title":"Protection of big data privacy","volume":"4","author":"Mehmood","year":"2016","journal-title":"IEEE Access"},{"key":"ref_4","unstructured":"Barbaro, M., Zeller, T., and Hansell, S. (New York Times, 2006). A face is exposed for AOL searcher no. 4417749, New York Times."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"51071","DOI":"10.1109\/ACCESS.2020.2980235","article-title":"A Survey on Privacy Properties for Data Publishing of Relational Data","volume":"8","author":"Zigomitros","year":"2020","journal-title":"IEEE Access"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1109\/69.979982","article-title":"Practical data-oriented microaggregation for statistical disclosure control","volume":"14","year":"2002","journal-title":"Knowl. Data Eng. IEEE Trans."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Torra, V. (2004). Microaggregation for Categorical Variables: A Median Based Approach. Privacy in Statistical Databases, Springer.","DOI":"10.1007\/978-3-540-25955-8_13"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"901","DOI":"10.1109\/TIFS.2013.2248728","article-title":"Distributed architecture with double-phase microaggregation for the private sharing of biomedical data in mobile health","volume":"8","author":"Solanas","year":"2013","journal-title":"IEEE Trans. Inf. Forensics Secur."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1109\/MCOM.2013.6525606","article-title":"The pursuit of citizens\u2019 privacy: A privacy-aware smart city is possible","volume":"51","author":"Solanas","year":"2013","journal-title":"IEEE Commun. Mag."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"1000","DOI":"10.1016\/j.jcss.2014.12.013","article-title":"A k-anonymous approach to privacy preserving collaborative filtering","volume":"81","author":"Casino","year":"2015","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"714","DOI":"10.1016\/j.camwa.2007.04.034","article-title":"A polynomial-time approximation to optimal multivariate microaggregation","volume":"55","author":"Solanas","year":"2008","journal-title":"Comput. Math. Appl."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"1043","DOI":"10.1109\/TKDE.2003.1209020","article-title":"A polynomial algorithm for optimal univariate microaggregation","volume":"15","author":"Hansen","year":"2003","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_13","unstructured":"Solanas, A., and Martinez, A. (September, January 28). VMDAV: A Multivariate Microaggregation With Variable Group Size. Proceedings of the 17th COMPSTAT Symposium of the IASC, Rome, Italy."},{"key":"ref_14","unstructured":"Shmoys, D.B., Lenstra, J., Kan, A.R., and Lawler, E.L. (1985). The Traveling Salesman Problem, John Wiley & Sons, Incorporated."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1137\/0206041","article-title":"An analysis of several heuristics for the traveling salesman problem","volume":"6","author":"Rosenkrantz","year":"1977","journal-title":"SIAM J. Comput."},{"key":"ref_16","unstructured":"Applegate, D.L., Bixby, R.E., Chvatal, V., and Cook, W.J. (2006). The Traveling Salesman Problem: A Computational Study, Princeton University Press."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1007\/s00778-006-0007-0","article-title":"Efficient multivariate data-oriented microaggregation","volume":"15","year":"2006","journal-title":"VLDB J."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"902","DOI":"10.1109\/TKDE.2005.112","article-title":"Minimum spanning tree partitioning algorithm for microaggregation","volume":"17","author":"Laszlo","year":"2005","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1007\/s10207-012-0158-5","article-title":"Efficient microaggregation techniques for large numerical data volumes","volume":"11","author":"Nin","year":"2012","journal-title":"Int. J. Inf. Secur."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"1866","DOI":"10.1016\/j.jss.2007.02.014","article-title":"TFRP: An efficient microaggregation algorithm for statistical disclosure control","volume":"80","author":"Chang","year":"2007","journal-title":"J. Syst. Softw."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"79158","DOI":"10.1109\/ACCESS.2020.2990296","article-title":"Associated attribute-aware differentially private data publishing via microaggregation","volume":"8","author":"Yang","year":"2020","journal-title":"IEEE Access"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"3256","DOI":"10.1016\/j.eswa.2009.09.054","article-title":"Density-based microaggregation for statistical disclosure control","volume":"37","author":"Lin","year":"2010","journal-title":"Expert Syst. Appl."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"1191","DOI":"10.1109\/TKDE.2011.242","article-title":"Successive group selection for microaggregation","volume":"25","author":"Panagiotakis","year":"2011","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"529","DOI":"10.1007\/s10489-013-0431-y","article-title":"Multivariate microaggregation by iterative optimization","volume":"39","author":"Mortazavi","year":"2013","journal-title":"Appl. Intell."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/j.knosys.2014.05.011","article-title":"Fast data-oriented microaggregation algorithm for large numerical datasets","volume":"67","author":"Mortazavi","year":"2014","journal-title":"Knowl. Based Syst."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"1161","DOI":"10.1002\/spe.992","article-title":"A survey on statistical disclosure control and micro-aggregation techniques for secure statistical databases","volume":"40","author":"Fayyoumi","year":"2010","journal-title":"Softw. Pract. Exp."},{"key":"ref_27","unstructured":"Heaton, B., and Mukherjee, S. (2011, January 1\u20132). Record Ordering Heuristics for Disclosure Control through Microaggregation. Proceedings of the International Conference on Advances in Communication and Information Technology, Amsterdam, The Netherlands."},{"key":"ref_28","first-page":"67","article-title":"Statistical disclosure control for microdata using the R-package sdcMicro","volume":"1","author":"Templ","year":"2008","journal-title":"Trans. Data Priv."},{"key":"ref_29","unstructured":"(2021, May 01). OpenStreetMap Contributors. Available online: https:\/\/planet.osm.org."},{"key":"ref_30","unstructured":"Nilsson, C. (2003). Heuristics for the Traveling Salesman Problem, Link\u00f6ping University. Available online: http:\/\/www.ida.liu.se\/~TDDB19\/reports_2003\/htsp.pdf."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/j.disopt.2016.01.005","article-title":"Branch-and-bound algorithms: A survey of recent advances in searching, branching, and pruning","volume":"19","author":"Morrison","year":"2016","journal-title":"Discret. Optim."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"1","DOI":"10.18637\/jss.v023.i02","article-title":"TSP-Infrastructure for the Traveling Salesperson Problem","volume":"23","author":"Hahsler","year":"2007","journal-title":"J. Stat. Softw."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1016\/S0377-2217(99)00284-2","article-title":"An effective implementation of the Lin\u2013Kernighan traveling salesman heuristic","volume":"126","author":"Helsgaun","year":"2000","journal-title":"Eur. J. Oper. Res."}],"container-title":["Symmetry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-8994\/13\/6\/916\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T06:05:06Z","timestamp":1760162706000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-8994\/13\/6\/916"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5,21]]},"references-count":33,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2021,6]]}},"alternative-id":["sym13060916"],"URL":"https:\/\/doi.org\/10.3390\/sym13060916","relation":{},"ISSN":["2073-8994"],"issn-type":[{"type":"electronic","value":"2073-8994"}],"subject":[],"published":{"date-parts":[[2021,5,21]]}}}