Utility-preserving differentially private skyline query

• Published in: Expert systems with applications 2022-01, Vol.187, p.115871, Article 115871
• Main Authors: Lan, Qiujun, Ma, Jiaqi, Yan, Ziqi, Li, Gang
• Format: Article
• Language: English
• Subjects: Clustering; Datasets; Decision making; Differential privacy; Privacy; Privacy preserving; Queries; Sensitivity; Skyline query; Spectral clustering
• ISSN: 0957-4174; 1873-6793
• DOI: 10.1016/j.eswa.2021.115871

Skyline query has been widely applied in multi-criterion decision making, whose potential privacy risk is practically concerned on some specific occasions. Differential Privacy (DP) is a rigorous privacy-preserving method for its robustness and reliability. Considering DP will deteriorate the data utility, this paper proposes the Individual Differential Privacy via Spectral Clustering (iDP-SC) to address the privacy leakage in skyline query. It shifts the calculation of the local sensitivity from the original dataset to the one processed by spectral clustering, and through this, the sensitivity is reduced as well as the calibrated noise. As a result, it maintain higher utility without sacrificing the privacy preservation provided by differential privacy. Furthermore, compared with existing work for privacy-preserving skyline query, the proposed iDP-SC avoids the disclosure of key information, while providing the quantitative analysis of privacy protection level. The performance of the proposed iDP-SC was examined through comparison with the DP and Individual Differential Privacy (iDP) on both real and synthetic datasets. The experimental results demonstrates the capability and effectiveness of the proposed approach. Along this line of research, future work could be extended to the situation where the curator is un-trusted, or the personalized privacy requirements of retailers etc. •A novel algorithm to address privacy risk in skyline query is proposed.•Concerns on the reduced data utility of differential privacy are solved.•Sensitivity can be further reduced by transforming the basis of local sensitivity.•Our algorithm can quantify the level of privacy protection for skyline query.•Our algorithm has obvious advantages when the privacy budget is small.