Vera Charlotte Cost

• The publication of statistical databases is subject to legal regulations, e.g. national statistical offices are only allowed to publish data if the data cannot be attributed to individuals. Achieving this privacy standard requires anonymizing the data prior to publication. However, data anonymization inevitably leads to a loss of information, which should be kept minimal. In this thesis, we analyze the anonymization method SAFE used in the German census in 2011 and we propose a novel integer programming-based anonymization method for nominal data. In the first part of this thesis, we prove that a fundamental variant of the underlying SAFE optimization problem is NP-hard. This justifies the use of heuristic approaches for large data sets. In the second part, we propose a new anonymization method belonging to microaggregation methods, specifically designed for nominal data. This microaggregation method replaces rows in a microdata set with representative values to achieve k-anonymity, ensuring each data row is identical to at least k − 1 other rows. In addition to the overall dissimilarities of the data rows, the method accounts for errors in resulting frequency tables, which are of high interest for nominal data in practice. The method employs a typical two-step structure: initially partitioning the data set into clusters and subsequently replacing all cluster elements with representative values to achieve k-anonymity. For the partitioning step, we propose a column generation scheme followed by a heuristic to obtain an integer solution, which is based on the dual information. For the aggregation step, we present a mixed-integer problem formulation to find cluster representatives. To this end, we take errors in a subset of frequency tables into account. Furthermore, we show a reformulation of the problem to a minimum edge-weighted maximal clique problem in a multipartite graph, which allows for a different perspective on the problem. Moreover, we formulate a mixed-integer program, which combines the partitioning and the aggregation step and aims to minimize the sum of chi-squared errors in frequency tables. Finally, an experimental study comparing the methods covered or developed in this work shows particularly strong results for the proposed method with respect to relative criteria, while SAFE shows its strength with respect to the maximum absolute error in frequency tables. We conclude that the inclusion of integer programming in the context of data anonymization is a promising direction to reduce the inevitable information loss inherent in anonymization, particularly for nominal data.
• Die Veröffentlichung statistischer Daten unterliegt rechtlichen Regelungen. Zum Beispiel dürfen nationale statistische Ämter Daten nur dann veröffentlichen, wenn diese keinen Einzelpersonen zugeordnet werden können. Um diesen Datenschutzstandard zu erreichen, ist es erforderlich, die Daten vor der Veröffentlichung zu anonymisieren. Allerdings führt die Anonymisierung unweigerlich zu einem Informationsverlust, der so gering wie möglich gehalten werden sollte. In dieser Arbeit analysieren wir die Anonymisierungsmethode SAFE, die beim deutschen Zensus 2011 verwendet wurde, und schlagen eine neue, auf ganzzahliger Programmierung basierende Anonymisierungsmethode für nominale Daten vor. Im ersten Teil dieser Arbeit beweisen wir, dass eine grundlegende Variante des SAFE zugrundeliegenden Optimierungsproblems NP-schwer ist. Dies rechtfertigt heuristische Ansätze für große Datensätze. Im zweiten Teil schlagen wir eine neue Anonymisierungsmethode vor, die zu Mikroaggregationsmethoden gehört und speziell für nominale Daten entwickelt wurde. Diese Methode ersetzt Zeilen in einem Mikrodatensatz durch repräsentative Werte, um k-Anonymität zu erreichen, das heißt sie stellt sicher, dass jede Datenzeile mit mindestens k − 1 anderen Zeilen identisch ist. Zusätzlich zu Unähnlichkeiten der Datenzeilen berücksichtigt die Methode Fehler in resultierenden Häufigkeitstabellen, die in der Praxis für nominale Daten von großem Interesse sind. Die Methode verwendet eine typische zweistufige Struktur: Zunächst wird der Datensatz in Cluster partitioniert und anschließend werden alle Clusterelemente durch repräsentative Werte ersetzt, um k-Anonymität zu erreichen. Für den Partitionierungsschritt schlagen wir einen Column Generation-Prozess vor, gefolgt von einer Heuristik, um eine ganzzahlige Lösung basierend auf den erhaltenen dualen Informationen zu erhalten. Für den Aggregationsschritt formulieren wir ein gemischt-ganzzahliges Optimierungsproblem, um Clusterrepräsentanten zu finden. Hier berücksichtigen wir Fehler in ausgewählten Häufigkeitstabellen. Wir zeigen zudem, wie dieses Problem umformuliert und als Problem aufgefasst werden kann, eine kostenminimale maximale Clique in einem multipartiten kantengewichteten Graphen zu finden, was eine andere Perspektive auf das Problem ermöglicht. Außerdem formulieren wir ein gemischt-ganzzahliges Programm, das den Partitionierungs- und den Aggregationsschritt kombiniert und darauf abzielt, die Summe der Chi-Quadrat-Fehler in Häufigkeitstabellen zu minimieren. Schließlich zeigt eine experimentelle Studie, die die in dieser Arbeit behandelten oder entwickelten Methoden vergleicht, besonders starke Ergebnisse für die vorgeschlagene Methode im Hinblick auf relative Kriterien, während SAFE seine Stärke in Bezug auf den maximalen absoluten Fehler in Häufigkeitstabellen zeigt. Wir kommen zu dem Schluss, dass die Einbeziehung der ganzzahligen Optimierung im Kontext der Datenanonymisierung ein vielversprechender Weg ist, um den unausweichlichen Informationsverlust durch Anonymisierung zu reduzieren, insbesondere bei nominalen Daten.