On the Costs and Benefits of Learned Indexing for Dynamic High-Dimensional Data: Extended Version
Authors:
Preprint
Abstract
One of the main challenges within the growing research area of learned indexing is the lack of adaptability to dynamically expanding datasets. This paper explores the dynamization of a static learned index for complex data through operations such as node splitting and broadening, enabling efficient adaptation to new data. Furthermore, we evaluate the trade-offs between static and dynamic approaches by introducing an amortized cost model to assess query performance in tandem with the build costs of the index structure, enabling experimental determination of when a dynamic learned index outperforms its static counterpart. We apply the dynamization method to a static learned index and demonstrate that its superior scaling quickly surpasses the static implementation in terms of overall costs as the database grows. This is an extended version of the paper presented at DAWAK 2025.Keywords
All Related Versions
This publication has 15 references indexed in Scilit:
- Survey of vector database management systemsThe VLDB Journal, 2024
- FLEX: A fast and light-weight learned index for kNN search in high-dimensional spaceInformation Sciences, 2024
- Learned Metric Index — Proposition of learned indexing for unstructured dataInformation Systems, 2021
- Overcoming catastrophic forgetting in neural networksProceedings of the National Academy of Sciences, 2017
- Approximate nearest neighbor algorithm based on navigable small world graphsInformation Systems, 2014
- Distinctive Image Features from Scale-Invariant KeypointsInternational Journal of Computer Vision, 2004
- D-Index: Distance Searching Index for Metric Data SetsMultimedia Tools and Applications, 2003
- Catastrophic Interference in Connectionist Networks: The Sequential Learning Problem1989
- Decomposable searching problems I. Static-to-dynamic transformationJournal of Algorithms, 1980
- The relative neighbourhood graph of a finite planar setPattern Recognition, 1980