K-Skyband query answering with differential privacy1

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 and performs finer partitions on the regions that are likely to contain k-skyband results.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.