Extended km-Anonymity for Randomization Applied to Binary Data
Masaya Kobayashi, Atsushi Fujioka, Koji Chida · 2023
Various models for evaluating anonymity have been proposed so far. Among them, k-anonymity is widely known as a typical anonymity measure, which guarantees that at least k individuals in a database have the same values. However, it is difficult to create highly useful anonymized data satisfying k-anonymity for high-dimensional data because of the curse of dimensionality. To overcome the problem, several approaches relaxing k-anonymity have been proposed, such as km-anonymity and σ-km-anonymity. Unfortunately, they can only evaluate deterministic anonymization methods.We propose Pkm-anonymity, a variant of km-anonymity, and prove that km-anonymity and Pkm-anonymity are equivalent in a deterministic privacy mechanism. This suggests that our Pkm-anonymity is an extension of kmanonymity. Also, we propose a km-anonymization method for binary data, unlike the previous approaches for non-binary data. The success probability and utility of the proposed method are examined with the number of attributes as a parameter. Our experiments show that the "curse of dimensionality" does not occur up to a dimensionality of 45 and that usefulness does not deteriorate in the range of dimensionality from 10 to 40.