Differentially Private Analysis of Outliers

This paper presents an investigation of differentially private analysis of distance-based outliers. Outlier detection aims to identify instances that are apparently distant from other instances. Meanwhile, the objective of differential privacy is to conceal the presence or absence of any particular instance. Outlier detection and privacy protection are therefore intrinsically conflicting tasks. In this paper, we present differentially private queries for counting outliers that appear in a given subspace, instead of reporting the outliers detected. Our analysis of the global sensitivity of outlier counts reveals that regular global sensitivity-based methods can make the outputs too noisy, particularly when the dimensionality of the given subspace is high. Noting that the counts of outliers are typically expected to be small compared to the number of data, we introduce a mechanism based on the smooth upper bound of the local sensitivity. This study is the first trial to ensure differential privacy for distance-based outlier analysis. The experimentally obtained results show that our method achieves better utility than global sensitivity-based methods do.

• Publication year

  2015

• Venue

  ECML/PKDD

• Publication date

  2015-07-24

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/978-3-319-23525-7_28arXiv 1507.06763
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Privacy-preserving LOF outlier detection

  2015cited by this paper
• Outlier Privacy

  2014cited by this paper
• Flexible and adaptive subspace search for outlier analysis

  2013cited by this paper
• Outlier Analysis

  2013cited by this paper
• Differentially Private Anomaly Detection with a Case Study on Epidemic Outbreak Detection

  2013cited by this paper
• A near-linear time approximation algorithm for angle-based outlier detection in high-dimensional data

  2012cited by this paper
• HiCS: High Contrast Subspaces for Density-Based Outlier Ranking

  2012cited by this paper
• A Distributed Solution for Privacy Preserving Outlier Detection

  2011cited by this paper
• Differential Privacy for Statistics: What we Know and What we Want to Learn

  2010cited by this paper
• Boosting and Differential Privacy

  2010cited by this paper
• High-Accuracy Semidefinite Programming Bounds for Kissing Numbers

  2009cited by this paper
• A New Local Distance-Based Outlier Detection Approach for Scattered Real-World Data

  2009cited by this paper
• Privacy Preserving Spatial Outlier Detection

  2008cited by this paper
• Smooth sensitivity and sampling in private data analysis

  2007influential reference
• Pseudorandom Bits for Polynomials

  2007cited by this paper
• Our Data, Ourselves: Privacy Via Distributed Noise Generation

  2006cited by this paper
• Calibrating Noise to Sensitivity in Private Data Analysis

  2006influential reference
• Oleg Musinの論文「The kissing number in four dimensions 」の紹介 (代数的組合せ論)

  2004cited by this paper
• Privacy-preserving outlier detection

  2004cited by this paper
• The Kissing Problem in Three Dimensions

  2004cited by this paper
• The kissing number in four dimensions

  2003cited by this paper
• Fast Smallest-Enclosing-Ball Computation in High Dimensions

  2003cited by this paper
• Finding Intensional Knowledge of Distance-Based Outliers

  1999cited by this paper
• Algorithms for Mining Distance-Based Outliers in Large Datasets

  1998cited by this paper

• Multi-source data outlier detection based on secure multi-party computation

  2026cites this paper
• Unifying Laplace Mechanism with Instance Optimality in Differential Privacy

  2025cites this paper
• Differential Privacy for Anomaly Detection: Analyzing the Trade-off Between Privacy and Explainability

  2024cites this paper
• Utility-Aware Time Series Data Release With Anomalies Under TLDP

  2024cites this paper
• A Framework for Privacy-Preserving White-Box Anomaly Detection using a Lattice-Based Access Control

  2023cites this paper
• DPI: Ensuring Strict Differential Privacy for Infinite Data Streaming

  2023cites this paper
• Trustworthy Anomaly Detection: A Survey

  2022cites this paper
• An Efficient Hashing-based Ensemble Method for Collaborative Outlier Detection

  2022cites this paper
• Diferentially Private k -Nearest Neighbor Missing Data Imputation

  2022cites this paper
• DPOAD: Differentially Private Outsourcing of Anomaly Detection through Iterative Sensitivity Learning

  2022cites this paper
• Tensions Between the Proxies of Human Values in AI

  2022cites this paper
• Data Regeneration From Poisoned Datasets

  2022cites this paper
• Position: Tensions Between the Proxies of Human Values in AI

  2022cites this paper
• Differentially Private Outlier Detection in Correlated Data

  2021cites this paper
• Differentially Private Normalizing Flows for Privacy-Preserving Density Estimation

  2021cites this paper
• PCOR: Private Contextual Outlier Release via Differentially Private Search

  2021cites this paper
• Achieving differential privacy for k-nearest neighbors based outlier detection by data partitioning

  2021cites this paper
• A Guide for Private Outlier Analysis

  2020cites this paper
• Robustness Guarantees for Mode Estimation with an Application to Bandits

  2020influential citation
• A Differentially Private Text Perturbation Method Using Regularized Mahalanobis Metric

  2020cites this paper
• Instance-optimality in differential privacy via approximate inverse sensitivity mechanisms

  2020cites this paper
• Robust Anomaly Detection and Backdoor Attack Detection Via Differential Privacy

  2019cites this paper
• Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimation

  2019cites this paper
• Differentially private nearest neighbor classification

  2017cites this paper