Consistency-aware scalable and authenticated learned index for range query
Author Identifier (ORCID)
Jianxin Li: https://orcid.org/0000-0002-9059-330X
Abstract
A corpus of recent work has revealed that authenticated query services have been under the spotlight due to the untrustworthiness of outsourced service provider. To enrich scalable functionality, there is an increasing demand for dynamically authenticated query. However, when implementing query and update simultaneously, traditional approaches heavily suffer from the inconsistency between verification digest and requested index and therefore are infeasible in reality. Moreover, the efficiency of storage, query, verification, and update is still a huge hinder when processing large scale data. To address these challenging issues, in this paper, we propose a novel idea of authenticated learned index that is carefully designed and actively optimized for authenticated query processing. Specifically, we first propose a version control update mechanism for consistency guarantee by maintaining historical index versions. Following this, we propose two basic authenticated learned indexes, i.e., query-friendly PVL-tree and update-friendly PVLB-tree, to support efficient scalable authenticated range query. Furthermore, to improve the efficiency, we introduce a hybrid index framework HPVL-tree based on two basic indexes. Extensive theoretical and experimental analysis demonstrate that our proposed HPVL-tree outperforms the state-of-the-art approaches by up to 2.28×, 3.96×, and 2.51× in search time, update time, and verification time, respectively. Moreover, the storage overhead and communication overhead occupy only 38 % and 2.25 % of existing approach, respectively.
Document Type
Conference Proceeding
Date of Publication
1-1-2025
Publication Title
Proceedings International Conference on Data Engineering
Publisher
IEEE
School
School of Business and Law
RAS ID
84304
Funders
New Generation Information Technology Innovation Project (2023IT080) / Basic Scientific Research Funds of Central Universities (300102404101, 300102404901) / National Natural Science Foundation of China (U22A2025, 62232007) / Liaoning Provincial Science and Technology Plan Project - Key R&D Department of Science and Technology (2023JH2/101300182)
Copyright
subscription content
First Page
3778
Last Page
3791
Comments
Cui, N., Wang, D., Zhu, H., Li, M., Cheng, J., Li, J., & Yang, X. (2025, May). Consistency-aware scalable and authenticated learned index for range query. In 2025 IEEE 41st International Conference on Data Engineering (ICDE) (pp. 3778-3791). https://doi.org/10.1109/ICDE65448.2025.00282