Articles producció científica> Enginyeria Informàtica i Matemàtiques

Improving multivariate microaggregation through hamiltonian paths and optimal univariate microaggregation

  • Dades identificatives

    Identificador: imarina:9217400
    Autors:
    Maya-Lopez, ArmandoCasino, FranSolanas, Agusti
    Resum:
    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
  • Altres:

    Autor segons l'article: Maya-Lopez, Armando; Casino, Fran; Solanas, Agusti
    Departament: Enginyeria Informàtica i Matemàtiques
    Autor/s de la URV: Alkhoury, Nadine / Casino Cembellín, Francisco José / Solanas Gómez, Agustín
    Paraules clau: Traveling salesman problem Statistical disclosure control Microaggregation Location privacy Graph theory Data privacy traveling salesman problem statistical disclosure control privacy location privacy graph theory data-oriented microaggregation data privacy algorithm
    Resum: 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.
    Àrees temàtiques: Visual arts and performing arts Physics and astronomy (miscellaneous) Multidisciplinary sciences Modeling and simulation Mathematics, interdisciplinary applications Mathematics (miscellaneous) Mathematics (all) Matemática / probabilidade e estatística General mathematics Engineering (miscellaneous) Computer science (miscellaneous) Ciência da computação Chemistry (miscellaneous) Arts and humanities (miscellaneous) Architecture Applied mathematics
    Accès a la llicència d'ús: https://creativecommons.org/licenses/by/3.0/es/
    Adreça de correu electrònic de l'autor: franciscojose.casino@urv.cat nadine.alkhoury@estudiants.urv.cat nadine.alkhoury@estudiants.urv.cat nadine.alkhoury@estudiants.urv.cat nadine.alkhoury@estudiants.urv.cat agusti.solanas@urv.cat
    Identificador de l'autor: 0000-0003-4296-2876 0000-0002-4881-6215
    Data d'alta del registre: 2024-10-12
    Versió de l'article dipositat: info:eu-repo/semantics/publishedVersion
    Enllaç font original: https://www.mdpi.com/2073-8994/13/6/916
    URL Document de llicència: https://repositori.urv.cat/ca/proteccio-de-dades/
    Referència a l'article segons font original: Symmetry-Basel. 13 (6): 916-
    Referència de l'ítem segons les normes APA: Maya-Lopez, Armando; Casino, Fran; Solanas, Agusti (2021). Improving multivariate microaggregation through hamiltonian paths and optimal univariate microaggregation. Symmetry-Basel, 13(6), 916-. DOI: 10.3390/sym13060916
    DOI de l'article: 10.3390/sym13060916
    Entitat: Universitat Rovira i Virgili
    Any de publicació de la revista: 2021
    Tipus de publicació: Journal Publications
  • Paraules clau:

    Applied Mathematics,Architecture,Arts and Humanities (Miscellaneous),Chemistry (Miscellaneous),Computer Science (Miscellaneous),Engineering (Miscellaneous),Mathematics (Miscellaneous),Mathematics, Interdisciplinary Applications,Modeling and Simulation,Multidisciplinary Sciences,Physics and Astronomy (Miscellaneous),Visual Arts and Performi
    Traveling salesman problem
    Statistical disclosure control
    Microaggregation
    Location privacy
    Graph theory
    Data privacy
    traveling salesman problem
    statistical disclosure control
    privacy
    location privacy
    graph theory
    data-oriented microaggregation
    data privacy
    algorithm
    Visual arts and performing arts
    Physics and astronomy (miscellaneous)
    Multidisciplinary sciences
    Modeling and simulation
    Mathematics, interdisciplinary applications
    Mathematics (miscellaneous)
    Mathematics (all)
    Matemática / probabilidade e estatística
    General mathematics
    Engineering (miscellaneous)
    Computer science (miscellaneous)
    Ciência da computação
    Chemistry (miscellaneous)
    Arts and humanities (miscellaneous)
    Architecture
    Applied mathematics
  • Documents:

  • Cerca a google

    Search to google scholar