%0 Conference Proceedings
%T Differentially Private K-Skyband Query Answering Through Adaptive Spatial Decomposition
%+ North Carolina State University [Raleigh] (NC State)
%+ Hamad Bin Khalifa University (HBKU)
%A Chen, Ling
%A Yu, Ting
%A Chirkova, Rada
%Z Part 2: Privacy
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 31th IFIP Annual Conference on Data and Applications Security and Privacy (DBSEC)
%C Philadelphia, PA, United States
%Y Giovanni Livraga
%Y Sencun Zhu
%I Springer International Publishing
%3 Data and Applications Security and Privacy XXXI
%V LNCS-10359
%P 142-163
%8 2017-07-19
%D 2017
%R 10.1007/978-3-319-61176-1_8
%K k-skyband query
%K Differential privacy
%K Adaptive spatial decomposition
%Z Computer Science [cs]Conference papers
%X 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.
%G English
%Z TC 11
%Z WG 11.3
%2 https://inria.hal.science/hal-01684359/document
%2 https://inria.hal.science/hal-01684359/file/453481_1_En_8_Chapter.pdf
%L hal-01684359
%U https://inria.hal.science/hal-01684359
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-WG
%~ IFIP-TC11
%~ IFIP-WG11-3
%~ IFIP-DBSEC
%~ IFIP-LNCS-10359