PriPL-Tree: Accurate Range Query for Arbitrary Distribution under Local Differential Privacy

Summary: PriPL-Tree: hierarchical LDP structure that models node distributions with piecewise-linear fits instead of the usual uniform-within-partition assumption, improving range-query accuracy with few segments. Multidimensional extension uses data-aware adaptive grids built from PriPL marginals. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h92e1b8602b311ac4
Venue: VLDB
Year: 2024
Pagerank: 5.1708619e-05
Overall Rank: 9,473 | 36.31%
DOI: 10.14778/3681954.3681981

Incoming Non-self Citations Over Time

Authors

1. Leixia Wang (Renmin University of China)
2. Qingqing Ye (Hong Kong Polytechnic University)
3. Haibo Hu (Hong Kong Polytechnic University)
4. Xiaofeng Meng (Renmin University of China)

BibTeX Citation

@article{wang_vldb24,
        title = {{PriPL-Tree: Accurate Range Query for Arbitrary Distribution under Local Differential Privacy}},
        author = {Wang, Leixia and Ye, Qingqing and Hu, Haibo and Meng, Xiaofeng},
        journal = {PVLDB},
        series = {{VLDB} '24},
        volume = {17},
        number = {11},
        pages = {3031--3044},
        doi = {10.14778/3681954.3681981},
        url = {https://doi.org/10.14778/3681954.3681981},
        year = {2024}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,418	Femur: A Flexible Framework for Fast and Secure Querying from Public Key-Value Store	2025	SIGMOD	5.3350162e-05
10,575	High Performance or Low Memory? An Updatable Learned Index Framework for Time-Space Tradeoff	2026	SIGMOD	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 18 of 18 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
121	Boosting the Accuracy of Differentially Private Histograms Through Consistency	2010	VLDB	0.00031089378
463	The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds	2020	VLDB	0.00017804544
558	Understanding Hierarchical Methods for Differentially Private Histograms	2013	VLDB	0.00016470707
779	FITing-Tree: A Data-aware Index Structure	2019	SIGMOD	0.00014030069
1,324	PrivTree: A Differentially Private Algorithm for Hierarchical Decompositions	2016	SIGMOD	0.00011023355
1,446	LISA: A Learned Index Structure for Spatial Data	2020	SIGMOD	0.00010629222
1,528	A Data- and Workload-Aware Algorithm for Range Queries Under Differential Privacy	2014	VLDB	0.00010349919
1,609	PriView: Practical Differentially Private Release of Marginal Contingency Tables	2014	SIGMOD	0.00010079578
1,713	Online Piece-wise Linear Approximation of Numerical Streams with Precision Guarantees	2009	VLDB	9.8143771e-05
1,888	Marginal Release Under Local Differential Privacy	2018	SIGMOD	9.4287112e-05
2,277	FINEdex: A Fine-grained Learned Index Scheme for Scalable and Concurrent Memory Systems	2022	VLDB	8.7075835e-05
2,336	Answering Multi-Dimensional Analytical Queries under Local Differential Privacy	2019	SIGMOD	8.6206562e-05
2,803	Estimating Numerical Distributions under Local Differential Privacy	2020	SIGMOD	7.9855215e-05
3,175	Answering Range Queries Under Local Differential Privacy	2019	VLDB	7.5673688e-05
4,214	Answering Multi-Dimensional Range Queries under Local Differential Privacy	2021	VLDB	6.7295366e-05
5,789	A Neural Database for Differentially Private Spatial Range Queries	2022	VLDB	5.9942738e-05
8,061	A workload-adaptive mechanism for linear queries under local differential privacy	2020	VLDB	5.3958211e-05
11,756	Trajectory Data Collection with Local Differential Privacy	2023	VLDB	4.9793485e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,061	A workload-adaptive mechanism for linear queries under local differential privacy	2020	VLDB
2	1,097	Privacy Preserving OLAP	2005	SIGMOD
3	2,336	Answering Multi-Dimensional Analytical Queries under Local Differential Privacy	2019	SIGMOD
4	1,528	A Data- and Workload-Aware Algorithm for Range Queries Under Differential Privacy	2014	VLDB
5	10,539	A General Framework for Per-record Differential Privacy	2026	SIGMOD
6	7,573	A Framework for Privacy Preserving Localized Graph Pattern Query Processing	2023	SIGMOD
7	4,214	Answering Multi-Dimensional Range Queries under Local Differential Privacy	2021	VLDB
8	1,324	PrivTree: A Differentially Private Algorithm for Hierarchical Decompositions	2016	SIGMOD
9	3,175	Answering Range Queries Under Local Differential Privacy	2019	VLDB
10	3,329	Answering Range Queries Under Local Differential Privacy	2019	SIGMOD