K-Anonymization as Spatial Indexing: Toward Scalable and Incremental Anonymization

In this paper, we introduce a novel approach to k-anonymization by making a new observation of a strikingly similar parallel between database indexing and k-anonymity. In general, however, the table to be published may contain more than one quasi-identifier attribute, so rather than use B⁺-trees, we suggest multidimensional spatial indexing as the basis for anonymization. We take a brief detour to discuss a measure for the quality of an anonymization algorithm.