  In this paper, we cast the classic problem of achieving k-anonymity for a
given database as a problem in algebraic topology. Using techniques from this
field of mathematics, we propose a framework for k-anonymity that brings new
insights and algorithms to anonymize a database. We begin by addressing the
simpler case when the data lies in a metric space. This case is instrumental to
introduce the main ideas and notation. Specifically, by mapping a database to
the Euclidean space and by considering the distance between datapoints, we
introduce a simplicial representation of the data and show how concepts from
algebraic topology, such as the nerve complex and persistent homology, can be
applied to efficiently obtain the entire spectrum of k-anonymity of the
database for various values of k and levels of generalization. For this
representation, we provide an analytic characterization of conditions under
which a given representation of the dataset is k-anonymous. We introduce a
weighted barcode diagram which, in this context, becomes a computational tool
to tradeoff data anonymity with data loss expressed as level of generalization.
Some simulations results are used to illustrate the main idea of the paper. We
conclude the paper with a discussion on how to extend this method to address
the general case of a mix of categorical and metric data.
