  Differential privacy provides a strong form of privacy and allows preserving
most of the original characteristics of the dataset. Utilizing these benefits
requires one to design specific differentially private data analysis
algorithms. In this work, we present three tree-based algorithms for mining
redescriptions while preserving differential privacy. Redescription mining is
an exploratory data analysis method for finding connections between two views
over the same entities, such as phenotypes and genotypes of medical patients,
for example. It has applications in many fields, including some, like health
care informatics, where privacy-preserving access to data is desired. Our
algorithms are the first differentially private redescription mining
algorithms, and we show via experiments that, despite the inherent noise in
differential privacy, it can return trustworthy results even in smaller
datasets where noise typically has a stronger effect.
