nach oben

International Journal of Information Security

Erschienen in:

23.10.2017 | Regular Contribution

Optimization algorithm for k-anonymization of datasets with low information loss

verfasst von: Keisuke Murakami, Takeaki Uno

Erschienen in: International Journal of Information Security | Ausgabe 6/2018

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Anonymization is the modification of data to mask the correspondence between a person and sensitive information in the data. Several anonymization models such as k-anonymity have been intensively studied. Recently, a new model with less information loss than existing models was proposed; this is a type of non-homogeneous generalization. In this paper, we present an alternative anonymization algorithm that further reduces the information loss using optimization techniques. We also prove that a modified dataset is checked whether it satisfies the k-anonymity by a polynomial-time algorithm. Computational experiments were conducted and demonstrated the efficiency of our algorithm even on large datasets.

Vorheriger Artikel Optimal noise functions for location privacy on continuous regions

Nächster Artikel OnionDNS: a seizure-resistant top-level domain

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Nur mit Berechtigung zugänglich

Sacharidis, D., Mouratidis, K., Papadias, D.: k-Anonymity in the presence of external databases. IEEE Trans. Knowl. Data Eng. 22(3), 392–403 (2010)CrossRef

Dalenius, T.: Finding a needle in a haystack or identifying anonymous census record. J. Off. Stat. 2(3), 329–336 (1986)

Wang, K., Yu, P.S., Chakraborty, S.: Bottom-up generalization: a data mining solution to privacy protection. In: Fourth IEEE International Conference on Data Mining, 2004. ICDM’04, pp. 249–256 (2004)

Samarati, P., Sweeney, L.: Generalizing data to provide anonymity when disclosing information. In: Proceedings of the 17th ACM SIGMOD-SIGACT-SIGART Symposium on the Principles of Database Systems, p. 188 (1998)

Fung, B., Wang, K., YU, P.: Top-down specialization for information and privacy preservation. In: Proceedings. 21st International Conference on Data Engineering, 2005. ICDE 2005. IEEE, pp. 205–216 (2005)

Samarati, P.: Protecting respondants identities in microdata release. IEEE Trans. Knowl. Data Eng. 13(6), 1010–1027 (2001)CrossRef

Sun, X., Li, M., Wang, H., Plank, A.: An efficient hash-based algorithm for minimal k-anonymity. In: Proceedings of the Thirty-First Australasian Conference on Computer Science, vol. 74, pp. 101–107 (2008)

Samarati, P., Sweeney, L.: Protecting privacy when disclosing information: \({k}\)-anonymity and its enforcement through generalization and suppression. Technical Report SRI-CSL-98–04, SRI Computer Science Laboratory (1998)

LeFevre, K., DeWitt, D.J., Ramakrishnan, R., Incognito: Efficient full-domain \({k}\)-anonymity. In: Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data, vol. 21, pp. 49–60 (2005)

10.

Machanavajjhala, A., Gehrke, J., Kifer, D.: l-Diversity: privacy beyond k-anonymity. ACM Trans. Knowl. Discov. Data 1(3), 1–52 (2007)

11.

Domingo-Ferrer, J.: Microaggregation for database and location privacy. In: Etzion, O., Kuflik, T., Motro, A. (eds.) Next Generation Information Technologies and Systems. Lecture Notes in Computer Science, vol. 4032. Springer, Berlin, Heidelberg, pp. 106–116 (2006)CrossRef

12.

Campan, A., Truta, T.M., Miller, J., Sinca, R.A.: A clustering approach for achieving data privacy. In: Proceedings of the International Data Mining Conference, pp. 321–330 (2007)

13.

Goldberg, A.V., Tarjan, R.E.: Efficient maximum flow algorithms. Commun. ACM 57(8), 82–89 (2014)CrossRef

14.

Aggarwal, G., Feder, T., Kenthapadi, K., Motwani, R., Panigrahy, R., Thomas, D., Zhu, A.: Anonymizing tables. In: Proceedings of the 10th International Conference on Database Theory, LNCS, 3363, pp. 246–258 (2005)

15.

Sweeney, L.: Achieving k-anonymity privacy protection using generalization and suppression. Int. J. Uncertain. Fuzziness Knowl. Based Syst. 10(5), 571–588 (2002)MathSciNetCrossRef

16.

Wong, W.K., Mamoulis, N., Cheung, D.W.-L.: Non-homogeneous generalization in privacy preserving data publishing. In: The ACM SIGMOD International Conference on Data Management (SIGMOD), pp. 747–758 (2010)

17.

Murakami, K., Uno, T.: A matching model and an algorithm for k-anonymity of large-scale data. In: Proceedings of the 15th Korea-Japan Joint Workshop on Algorithms and Computation, pp. 154–160 (2012)

18.

Shmueli, E., Tassa, T., Wasserstein, R., Shapira, B., Rokach, L.: Limiting disclosure of sensitive data in sequential releases of databases. Inf. Sci. 191, 98–127 (2012)CrossRef

19.

Shmueli, E., Tassa, T.: Privacy by diversity in sequential releases of databases. Inf. Sci. 298, 344–372 (2015)CrossRef

20.

Goldberg, A.V.: An Efficient implementation of a scaling minimum-cost flow algorithm. J. Algorithms 22(1), 1–29 (1997)MathSciNetCrossRef

21.

Hall, P.: On representatives of subsets. J. Lond. Math. Soc. 10(1), 26–30 (1935)CrossRef

22.

Goldberg, A.V., Tarjan, R.E.: Finding minimum-cost circulations by canceling negative cycles. J. ACM 36(4), 873–886 (1989)MathSciNetCrossRef

23.

Sokkalingam, P.T.: New polynomial-time cycle-canceling algorithms for minimum cost flows. Ph.D. Thesis, Massachusetts Institute of Technology, Cambridge, MA 02139, USA (1997)

24.

Uno, T.: Multi-sorting algorithm for finding pairs of similar short substrings from large-scale string data. Knowl. Inf. Syst. 25(2), 229–251 (2010)CrossRef

Titel: Optimization algorithm for k-anonymization of datasets with low information loss
verfasst von: Keisuke Murakami
Takeaki Uno
Publikationsdatum: 23.10.2017
Verlag: Springer Berlin Heidelberg
Erschienen in: International Journal of Information Security / Ausgabe 6/2018
Print ISSN: 1615-5262
Elektronische ISSN: 1615-5270
DOI: https://doi.org/10.1007/s10207-017-0392-y

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 6/2018

A framework for estimating information security risk assessment method completeness

Comparing apples with apples: performance analysis of lattice-based authenticated key exchange protocols

DomainProfiler: toward accurate and early discovery of domain names abused in future

OnionDNS: a seizure-resistant top-level domain

Talos: no more ransomware victims with formal methods

Optimal noise functions for location privacy on continuous regions