Answering Range Queries Under Local Differential Privacy

Summary: Introduces hierarchical-histogram and Haar-wavelet methods for range queries under local differential privacy, where users perturb data before aggregation. Provides variance guarantees and shows wavelets excel at high privacy, while hierarchies win under weaker privacy. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 12000
Venue: VLDB
Year: 2019
Pagerank: 7.7357038e-05
Overall Rank: 3,121 | 78.59%
DOI: 10.14778/3339490.3339496

Incoming Non-self Citations Over Time

Authors

1. Graham Cormode (University of Warwick)
2. Tejas Kulkarni (University of Warwick)
3. Divesh Srivastava (AT&T)

BibTeX Citation

@article{cormode_vldb19,
        title = {{Answering Range Queries Under Local Differential Privacy}},
        author = {Cormode, Graham and Kulkarni, Tejas and Srivastava, Divesh},
        journal = {PVLDB},
        series = {{VLDB} '19},
        volume = {12},
        number = {10},
        pages = {1126--1138},
        doi = {10.14778/3339490.3339496},
        url = {https://doi.org/10.14778/3339490.3339496},
        year = {2019}
}

Incoming Citations (Sorted by Pagerank)

Showing 14 of 14 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,698	Rosetta: A Robust Space-Time Optimized Range Filter for Key-Value Stores	2020	SIGMOD	8.2450522e-05
3,143	Frequency Estimation under Local Differential Privacy	2021	VLDB	7.7137142e-05
3,166	LDP-IDS: Local Differential Privacy for Infinite Data Streams	2022	SIGMOD	7.6752517e-05
4,132	Answering Multi-Dimensional Range Queries under Local Differential Privacy	2021	VLDB	6.8832571e-05
5,595	Privacy Amplification via Shuffling: Unified, Simplified, and Tightened	2024	VLDB	6.1548101e-05
6,951	RM2: Answer Counting Queries Efficiently under Shuffle Differential Privacy	2025	SIGMOD	5.7303405e-05
7,488	Frequency Estimation Under Multiparty Differential Privacy: One-shot and Streaming	2022	VLDB	5.6072422e-05
7,898	A workload-adaptive mechanism for linear queries under local differential privacy	2020	VLDB	5.5196369e-05
8,106	SpaceSaving±: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model	2022	VLDB	5.4853605e-05
8,616	CoopStore: Optimizing Precomputed Summaries for Aggregation	2020	VLDB	5.4004741e-05
8,719	DPXPlain: Privately Explaining Aggregate Query Answers	2023	VLDB	5.3774243e-05
9,300	PriPL-Tree: Accurate Range Query for Arbitrary Distribution under Local Differential Privacy	2024	VLDB	5.289545e-05
11,230	AAA: an Adaptive Mechanism for Locally Differentially Private Mean Estimation	2024	VLDB	5.093636e-05
11,462	Federated Calibration and Evaluation of Binary Classifiers	2023	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 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
567	Understanding Hierarchical Methods for Differentially Private Histograms	2013	VLDB	0.00016420715
1,837	Marginal Release Under Local Differential Privacy	2018	SIGMOD	9.6443703e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,451	Enhancing Local Differential Privacy Accuracy by Exploiting Inherent Uncertainty	2026	SIGMOD
2	2,279	Answering Multi-Dimensional Analytical Queries under Local Differential Privacy	2019	SIGMOD
3	3,143	Frequency Estimation under Local Differential Privacy	2021	VLDB
4	10,335	A General Framework for Per-record Differential Privacy	2026	SIGMOD
5	1,837	Marginal Release Under Local Differential Privacy	2018	SIGMOD
6	567	Understanding Hierarchical Methods for Differentially Private Histograms	2013	VLDB
7	9,300	PriPL-Tree: Accurate Range Query for Arbitrary Distribution under Local Differential Privacy	2024	VLDB
8	1,504	A Data- and Workload-Aware Algorithm for Range Queries Under Differential Privacy	2014	VLDB
9	4,132	Answering Multi-Dimensional Range Queries under Local Differential Privacy	2021	VLDB
10	3,260	Answering Range Queries Under Local Differential Privacy	2019	SIGMOD