Answering Federated Range Queries with Local Differential Privacy

Answering range queries under local differential privacy (LDP) is a well-studied problem, which enables service providers to gain insights into decentralized data distributions. However, existing approaches operate exclusively in a single-party setting and prove challenging to extend to practical cross-party environments. In this paper we study the problem of federated range queries under LDP, which addresses cross-party range queries in decentralized settings. Applying LDP to federated range queries amplifies statistical heterogeneity challenges, as utility deterioration stems from not only the accumulated LDP noise, but also the unrealistic uniform- or linear-distribution assumption in existing methods. Our solution, the private cubic spline (PrivCS) mechanism, employs a hierarchical interval tree structure to model the underlying data distribution and accurately answer arbitrary range queries, effectively addressing the problem while satisfying $\epsilon$-LDP. Additionally, we introduce the collaborative frequency filtering aggregation that adaptively calibrates and masks frequency estimates by leveraging relationships among across-party frequencies and analyzing pruning bias, thereby reducing the cumulative noise. To the best of our knowledge, this is the first study to explore federated range queries in cross-party scenarios, under the stringent LDP guarantee. Comprehensive experiments on both real-world and synthetic datasets demonstrate the effectiveness of our mechanism.