PriPL-Tree: Accurate Range Query for Arbitrary Distribution under Local Differential Privacy
<|reference_start|>PriPL-Tree: Accurate Range Query for Arbitrary Distribution under Local Differential Privacy: Answering range queries in the context of Local Differential Privacy (LDP) is a widely studied problem in Online Analytical Processing (OLAP). Existing LDP solutions all assume a uniform data distribution within each domain partition, which may not align with real-world scenarios where data distribution is varied, resulting in inaccurate estimates. To address this problem, we introduce PriPL-Tree, a novel data structure that combines hierarchical tree structures with piecewise linear (PL) functions to answer range queries for arbitrary distributions. PriPL-Tree precisely models the underlying data distribution with a few line segments, leading to more accurate results for range queries. Furthermore, we extend it to multi-dimensional cases with novel data-aware adaptive grids. These grids leverage the insights from marginal distributions obtained through PriPL-Trees to partition the grids adaptively, adapting the density of underlying distributions. Our extensive experiments on both real and synthetic datasets demonstrate the effectiveness and superiority of PriPL-Tree over state-of-the-art solutions in answering range queries across arbitrary data distributions.<|reference_end|>
@article{wang2024pripl-tree:,
    title={PriPL-Tree: Accurate Range Query for Arbitrary Distribution under Local
  Differential Privacy},
    author={Leixia Wang, Qingqing Ye, Haibo Hu, Xiaofeng Meng},
    journal={arXiv preprint arXiv:2407.13532},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.13532},
    primaryClass={cs.CR cs.DB}
}