Privacy preserving data publishing has attracted considerable research
interest in recent years. Among the existing solutions, {\em
$\epsilon$-differential privacy} provides one of the strongest privacy
guarantees. Existing data publishing methods that achieve
$\epsilon$-differential privacy, however, offer little data utility. In
particular, if the output dataset is used to answer count queries, the noise in
the query answers can be proportional to the number of tuples in the data,
which renders the results useless.