In recent years, a major thread of research on kanonymity has focused on developing more flexible generalization schemes that produce higher-quality datasets. In this paper we introduce three new generalization schemes that improve on existing schemes, as well as algorithms enumerating valid generalizations in these schemes. We also introduce a taxonomy for generalization schemes and a new cost metric for measuring information loss. We present a bottom-up search strategy for finding optimal anonymizations. This strategy works particularly well when the value of k is small. We show the feasibility of our approach through experiments on real census data.