Anonymizing Collections of Tree-Structured Data

Collections of real-world data usually have implicit or explicit structural relations. For example, databases link records through foreign keys, and XML documents express associations between different values through syntax. Privacy preservation, until now, has focused either on data with a very simple structure, e.g. relational tables, or on data with very complex structure e.g. social network graphs, but has ignored intermediate cases, which are the most frequent in practice. In this work, we focus on tree structured data. Such data stem from various applications, even when the structure is not directly reflected in the syntax, e.g. XML documents. A characteristic case is a database where information about a single person is scattered amongst different tables that are associated through foreign keys. The paper defines k((m,n))-anonymity, which provides protection against identity disclosure and proposes a greedy anonymization heuristic that is able to sanitize large datasets. The algorithm and the quality of the anonymization are evaluated experimentally.