Consistency-Aware Scalable and Authenticated Learned Index for Range Query

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\times, 3.96\times$, and$2.51\times$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.