Abstract
When releasing microdata for research purposes, one needs to preserve the privacy of respondents while maximizing
data utility. An approach that has been studied extensively in recent years is to use anonymization techniques such as gen-
eralization and suppression to ensure that the released data table satisfies the k-anonymity property. A major thread of
research in this area aims at developing more flexible generalization schemes and more efficient searching algorithms to
find better anonymizations (i.e., those that have less information loss).
This paper presents three new generalization schemes that are more flexible than existing schemes. This flexibility can
lead to better anonymizations. We present a taxonomy of generalization schemes and discuss their relationship. We present
enumeration algorithms and pruning techniques for finding optimal generalizations in the new schemes. Through exper-
iments on real census data, we show that more-flexible generalization schemes produce higher-quality anonymizations and
the bottom-up works better for small k values and small number of quasi-identifier attributes than the top-down approach.
