Publishing microdata raises concerns of individual privacy. When there exist outlier records in the microdata, the distinguishability of the outliers enables their privacy to be easier to be compromised than that of regular ones. However, none of the existing anonymization techniques can provide sufficient protection to the privacy of the outliers. This talk describes our work on the problem of anonymizing the microdata that contains outliers. We describe our solutions that efficiently anonymize the microdata with low information loss.