STUBRIN: A Spatio-Temporal Prediction Enhanced Learned Index for Spatial Data

The cross-fertilization of the fast-developing AI technology and spatial indexing has given rise to spatial learned indexes. However, these indexes rely on historical data distributions to build models, which limits their ability to anticipate data that has not yet arrived. To address this, we propose a novel Spatio-Temporal Update Method (STUM) that enhances conventional spatial learned indexes by introducing a Spatial Delta Area (SDA) for updates without altering their hierarchical structure. STUM learns spatio-temporal auto-correlation from historical data and integrates predicted future distributions. We apply STUM to the Spatial Learned Block Range INdex (SLBRIN), resulting in the development of the Spatio-Temporal Updatable learned Block Range INdex (STUBRIN), which adopts Revmap to integrate spatio-temporal sequence predictions with the spatial block range. STUBRIN optimizes the retraining process by learning the temporal continuity from spatial distribution and fusing it into the error threshold control mechanism and historical delta learning mechanism. Our results show that STUBRIN achieves 1.9-2.4×, 1.8-13.3×, 3.4-6.7× better build, query and update performance compared to state-ofthe-art methods. Additionally, STUBRIN offers superior query and update stability. For concurrent learned indexes, we have also designed parallel scheduling for STUBRIN, which improves build, query and update performance by 6.2-6.8×, 0.3-4.2×, 2.6-5.5×, without increasing the index size.