Advances in information technology, and its use in research, are increasing both the need for anonymized data and the risks of poor anonymization. In this thesis, we point out some questions raised by current anonymization techniques such as (a) support for additional adversary models and the difficulty of measuring privacy provided, (b) flexibility of algorithms-generalizations with respect to a utility cost metric, and (c) working with complex data. To address these issues, (a) We propose a human understandable privacy notion, δ- presence ; (b) We increase flexibility by introducing a new family of algorithms, clustering-based anonymity algorithms and two new types of generalizations, natural domain generalizations, generalizations with probability distributions. We also point out weaknesses such as metric-utility anomalies ; (c) We extend the definitions of current anonymization techniques for multirelational and spatio-temporal setting by presenting multirelational k-anonymity, and trajectory anonymity