TY  - JOUR
T1  - Beyond Traditional Search: SIMD-Optimized Correction for Learned Index
AU  - Oh, Yeojin 
AU  - Kim, Nakyeong 
AU  - Choi, Jongmoo 
AU  - Yoo, Seehwan 
JO  - Journal of KIISE, JOK
PY  - 2025
DA  - 2025/1/14
DO  - 10.5626/JOK.2025.52.5.363
KW  - learned index
KW  - recursive model indexes (RMI)
KW  - adaptive learned index(ALEX)
KW  - Search Algorithm
KW  - single instruction multi data(SIMD)
KW  - linear search
KW  - binary search
KW  - model-biased search
AB  - To address the limitations of traditional indexing techniques, this study examines the search performance of machine learning-based Learned Indexes, focusing on the read-only RMI and the modifiable ALEX We propose a SIMD-based optimization technique to minimize the overhead incurred during the correction phase, which accounts for over 80% of the total search time. Learned Indexes operate in two phases: prediction and correction. In our experiments with RMI, we found that when the error range is large, the SIMD Branchless Binary Search capable of quickly narrowing down the search range outperforms other methods. In contrast. when the error range is small, the model prediction-based SIMD Linear Search demonstrates superior performance. For ALEX, which maintains a relatively constant error range, the straightforward SIMD Linear Search proved to be the most efficient compared to more complex search techniques. These results underscore the importance of choosing the right search algorithm based on the dataset’s error range, index size, and density to achieve optimal performance.