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: 13708
Venue: VLDB
Year: 2024
Pagerank: 5.289545e-05
Overall Rank: 9,300 | 36.20%
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,249	Femur: A Flexible Framework for Fast and Secure Querying from Public Key-Value Store	2025	SIGMOD	5.4574671e-05
10,378	High Performance or Low Memory? An Updatable Learned Index Framework for Time-Space Tradeoff	2026	SIGMOD	5.093636e-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.00031639377
477	The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds	2020	VLDB	0.00017851226
567	Understanding Hierarchical Methods for Differentially Private Histograms	2013	VLDB	0.00016420715
790	FITing-Tree: A Data-aware Index Structure	2019	SIGMOD	0.0001401445
1,308	PrivTree: A Differentially Private Algorithm for Hierarchical Decompositions	2016	SIGMOD	0.00011216361
1,418	LISA: A Learned Index Structure for Spatial Data	2020	SIGMOD	0.00010835539
1,504	A Data- and Workload-Aware Algorithm for Range Queries Under Differential Privacy	2014	VLDB	0.00010548904
1,583	PriView: Practical Differentially Private Release of Marginal Contingency Tables	2014	SIGMOD	0.00010292522
1,688	Online Piece-wise Linear Approximation of Numerical Streams with Precision Guarantees	2009	VLDB	0.00010003536
1,837	Marginal Release Under Local Differential Privacy	2018	SIGMOD	9.6443703e-05
2,233	FINEdex: A Fine-grained Learned Index Scheme for Scalable and Concurrent Memory Systems	2022	VLDB	8.8968964e-05
2,279	Answering Multi-Dimensional Analytical Queries under Local Differential Privacy	2019	SIGMOD	8.8155688e-05
2,749	Estimating Numerical Distributions under Local Differential Privacy	2020	SIGMOD	8.1688076e-05
3,121	Answering Range Queries Under Local Differential Privacy	2019	VLDB	7.7357038e-05
4,132	Answering Multi-Dimensional Range Queries under Local Differential Privacy	2021	VLDB	6.8832571e-05
6,804	A Neural Database for Differentially Private Spatial Range Queries	2022	VLDB	5.768025e-05
7,898	A workload-adaptive mechanism for linear queries under local differential privacy	2020	VLDB	5.5196369e-05
11,444	Trajectory Data Collection with Local Differential Privacy	2023	VLDB	5.093636e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,898	A workload-adaptive mechanism for linear queries under local differential privacy	2020	VLDB
2	1,074	Privacy Preserving OLAP	2005	SIGMOD
3	2,279	Answering Multi-Dimensional Analytical Queries under Local Differential Privacy	2019	SIGMOD
4	1,504	A Data- and Workload-Aware Algorithm for Range Queries Under Differential Privacy	2014	VLDB
5	10,335	A General Framework for Per-record Differential Privacy	2026	SIGMOD
6	8,586	A Framework for Privacy Preserving Localized Graph Pattern Query Processing	2023	SIGMOD
7	4,132	Answering Multi-Dimensional Range Queries under Local Differential Privacy	2021	VLDB
8	1,308	PrivTree: A Differentially Private Algorithm for Hierarchical Decompositions	2016	SIGMOD
9	3,121	Answering Range Queries Under Local Differential Privacy	2019	VLDB
10	3,260	Answering Range Queries Under Local Differential Privacy	2019	SIGMOD