A Scalable Learned Index Scheme in Storage Systems
This work addresses scalability challenges in learned indexes for storage systems, offering incremental improvements in insertion performance and ease of retraining.
The paper tackles the scalability issues of learned indexes, such as heavy inter-model dependency and expensive retraining, by proposing a scheme that constructs independent linear regression models based on data distribution. Experimental results show that AIDEL improves insertion performance by about 2x compared to state-of-the-art schemes while maintaining comparable lookup performance and supporting scalability.
Index structures are important for efficient data access, which have been widely used to improve the performance in many in-memory systems. Due to high in-memory overheads, traditional index structures become difficult to process the explosive growth of data, let alone providing low latency and high throughput performance with limited system resources. The promising learned indexes leverage deep-learning models to complement existing index structures and obtain significant memory savings. However, the learned indexes fail to become scalable due to the heavy inter-model dependency and expensive retraining. To address these problems, we propose a scalable learned index scheme to construct different linear regression models according to the data distribution. Moreover, the used models are independent so as to reduce the complexity of retraining and become easy to partition and store the data into different pages, blocks or distributed systems. Our experimental results show that compared with state-of-the-art schemes, AIDEL improves the insertion performance by about 2$\times$ and provides comparable lookup performance, while efficiently supporting scalability.