Skip to Main content Skip to Navigation
Conference papers

Differentially Private K-Skyband Query Answering Through Adaptive Spatial Decomposition

Abstract : Given a set of multi-dimensional points, a $$k$$-skyband query retrieves those points dominated by no more than k other points. $$k$$-skyband queries are an important type of multi-criteria analysis with diverse applications in practice. In this paper, we investigate techniques to answer $$k$$-skyband queries with differential privacy. We first propose a general technique BBS-Priv, which accepts any differentially private spatial decomposition tree as input and leverages data synthesis to answer $$k$$-skyband queries privately. We then show that, though quite a few private spatial decomposition trees are proposed in the literature, they are mainly designed to answer spatial range queries. Directly integrating them with BBS-Priv would introduce too much noise to generate useful $$k$$-skyband results. To address this problem, we propose a novel spatial decomposition technique k-skyband tree specially optimized for k-skyband queries, which partitions data adaptively based on the parameter k. We further propose techniques to generate a k-skyband tree over spatial data that satisfies differential privacy, and combine BBS-Priv with the private k-skyband tree to answer $$k$$-skyband queries. We conduct extensive experiments based on two real-world datasets and three synthetic datasets that are commonly used for evaluating $$k$$-skyband queries. The results show that the proposed scheme significantly outperforms existing differentially private spatial decomposition schemes and achieves high utility when privacy budgets are properly allocated.
Document type :
Conference papers
Complete list of metadata

Cited literature [36 references]  Display  Hide  Download

https://hal.inria.fr/hal-01684359
Contributor : Hal Ifip <>
Submitted on : Monday, January 15, 2018 - 2:07:27 PM
Last modification on : Wednesday, May 20, 2020 - 11:48:11 AM
Long-term archiving on: : Wednesday, May 23, 2018 - 8:51:37 PM

File

453481_1_En_8_Chapter.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Ling Chen, Ting Yu, Rada Chirkova. Differentially Private K-Skyband Query Answering Through Adaptive Spatial Decomposition. 31th IFIP Annual Conference on Data and Applications Security and Privacy (DBSEC), Jul 2017, Philadelphia, PA, United States. pp.142-163, ⟨10.1007/978-3-319-61176-1_8⟩. ⟨hal-01684359⟩

Share

Metrics

Record views

340

Files downloads

192