Organizations collect increasing amounts of high-dimensional data about individuals. Examples are health record datasets containing diagnosis information, marketing datasets containing products purchased by customers, and web datasets containing check-ins in social networks. The sharing of such data is increasingly needed to support applications and/or satisfy policies and legislation. However, the high dimensionality of data makes their anonymization difficult, both from an effectiveness and from an efficiency point of view. In this talk, I will illustrate the problem and briefly review the main techniques used in the anonymization of high-dimensional data. Subsequently, I will present a class of methods we have been developing for anonymizing complex, high-dimensional data and their application to the healthcare domain.