A Workload-Aware Encrypted Index for Efficient Privacy-Preserving Range Queries

Summary: Introduces P³RQ-Bitmap and P³RQ-WBTree, encrypted range-query indexes combining PRF-based comparisons with workload-aware optimization. Adaptive partitioning, gradient-descent cost modeling, and dual updates yield up to 83× faster queries than prior privacy-preserving schemes. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 14556
Venue: VLDB
Year: 2026
Pagerank: 5.093636e-05
Overall Rank: 10,610 | 27.21%
DOI: 10.14778/3785297.3785313

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Dong Wang (Chang'an University)
2. Ningning Cui (Chang'an University)
3. Jianxin Li (Edith Cowan University)
4. Jianzhong Qi (University of Melbourne)
5. Jianliang Xu (Hong Kong Baptist University)
6. Hui Lu (Guangdong University of Technology)

BibTeX Citation

@article{wang_vldb26,
        title = {{A Workload-Aware Encrypted Index for Efficient Privacy-Preserving Range Queries}},
        author = {Wang, Dong and Cui, Ningning and Li, Jianxin and Qi, Jianzhong and Xu, Jianliang and Lu, Hui},
        journal = {PVLDB},
        series = {{VLDB} '26},
        volume = {19},
        number = {4},
        pages = {740--752},
        doi = {10.14778/3785297.3785313},
        url = {https://doi.org/10.14778/3785297.3785313},
        year = {2026}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 15 of 15 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
43	The Case for Learned Index Structures	2018	SIGMOD	0.00046060254
310	Order Preserving Encryption for Numeric Data	2004	SIGMOD	0.00021766789
447	ALEX: An Updatable Adaptive Learned Index	2020	SIGMOD	0.00018322593
873	Learning Multi-dimensional Indexes	2020	SIGMOD	0.00013481915
1,174	Tsunami: A Learned Multi-dimensional Index for Correlated Data and Skewed Workloads	2021	VLDB	0.00011817414
1,551	Updatable Learned Index with Precise Positions	2021	VLDB	0.00010381398
1,615	Arx: An Encrypted Database using Semantically Secure Encryption	2019	VLDB	0.00010214058
2,279	Answering Multi-Dimensional Analytical Queries under Local Differential Privacy	2019	SIGMOD	8.8155688e-05
4,132	Answering Multi-Dimensional Range Queries under Local Differential Privacy	2021	VLDB	6.8832571e-05
4,300	DILI: A Distribution-Driven Learned Index	2023	VLDB	6.773869e-05
4,751	The RLR-Tree: A Reinforcement Learning Based R-Tree for Spatial Data	2023	SIGMOD	6.5241784e-05
6,459	LMSFC: A Novel Multidimensional Index based on Learned Monotonic Space Filling Curves	2023	VLDB	5.8727182e-05
8,048	WISK: A Workload-aware Learned Index for Spatial Keyword Queries	2023	SIGMOD	5.5003171e-05
8,200	Waffle: A Workload-Aware and Query-Sensitive Framework for Disk-Based Spatial Indexing	2023	VLDB	5.4677285e-05
9,574	DITIR: Distributed Index for High Throughput Trajectory Insertion and Real-time Temporal Range Query	2017	VLDB	5.2528121e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,128	A Comparative Evaluation of Order-Revealing Encryption Schemes and Secure Range-Query Protocols	2019	VLDB
2	6,797	Efficient Searchable Encryption Through Compression	2018	VLDB
3	12,324	A Moving-Object Index for Efficient Query Processing with Peer-Wise Location Privacy	2012	VLDB
4	6,458	Workload-Aware Indexing of Continuously Moving Objects	2009	VLDB
5	8,531	Adaptive Indexing over Encrypted Numeric Data	2016	SIGMOD
6	1,310	A Privacy-Preserving Index for Range Queries	2004	VLDB
7	6,537	Range Search over Encrypted Multi-Attribute Data	2023	VLDB
8	1,504	A Data- and Workload-Aware Algorithm for Range Queries Under Differential Privacy	2014	VLDB
9	4,625	Practical Private Range Search Revisited	2016	SIGMOD
10	5,102	Fast Range Query Processing with Strong Privacy Protection for Cloud Computing	2014	VLDB