Answering Range Queries for Arbitrary Distribution under Shuffled Differential Privacy

Accurately answering range queries while protecting user privacy is critical in large-scale data collection scenarios. Current solutions for this problem based on local or shuffled differential privacy often use hierarchical trees, grids, and matrix mechanisms, which rely on domain decomposition and assume uniform distribution within sub-domains, resulting in significant accumulated noise errors and non-uniform errors when encountering non-uniform data distributions. To solve this problem, we propose a data distribution-aware structure in the shuffle model of differential privacy, called PriPL-Tree*. This structure uses a piecewise linear function to fit the data, eliminate non-uniform errors, and reduce noise, thanks to its concise tree structure and privacy amplification from shuffling. To build this tree with a balance of privacy, accuracy, and efficiency, we devise a novel node frequency estimation protocol for enhanced privacy amplification, a numerically optimized tree construction method for efficiency, and a weighted tree optimization method for improved accuracy. Additionally, we combine PriPL-Tree* with grids to adapt to multi-dimensional scenarios with optimally and non-uniformly allocated privacy budgets among dimensions. Through rigorous theoretical analysis and extensive experiments, we demonstrate the effectiveness and efficiency of our methods.