Differentially Private Outlier Detection in Correlated Data

The detection of outliers has become increasingly important for the control and monitoring of large-scale networked systems such as transportation and smart grids. Data from these systems, such as location traces or power consumption, are collected from individual agents, and are often privacy-sensitive. Furthermore, the networked nature of these systems results in the data of different individuals being correlated with each other. In this paper, we use the concept of differential privacy to design a privacy-preserving algorithm for outlier detection in correlated data. We determine analytic formulas to evaluate the performance of the proposed differentially private algorithm, and we analyze the trade-off between privacy level and detection accuracy. We illustrate our methodology using an example based on outlier detection in household electricity usage data.