Abstract
The purpose of this paper is proposing a novel search mechanism, called SLR (Segmented Linear Regression) search, based on the concept of learned index. It is motivated by our observation that a lot of big data, collected and used by previous studies, have a linearity property, meaning that keys and their stored locations show a strong linear correlation. This observation leads us to design SLR search where we apply segmentation into the well-known machine learning algorithm, linear regression, for identifying a location from a given key. We devise two segmentation techniques, equal-size and error-aware, with the consideration of both prediction accuracy and segmentation overhead. We implement our proposal in LevelDB, Google’s key-value store, and verify that it can improve search performance by up to 12.7%. In addition, we find that the equal-size technique provides efficiency in training while the error-aware one is tolerable to noisy data.
Funding Information
  • Institute of Information and communications Technology Planning and evaluation (IITP) (No. 2021-0-01475, No. NRF-2020R1A2C1006331, 2022R1A2C1006050)
  • Korea Government (MSIT) (No. 2021-0-01475, No. NRF-2020R1A2C1006331, 2022R1A2C1006050)
  • National Research Foundation of Korea (NRF) (No. 2021-0-01475, No. NRF-2020R1A2C1006331, 2022R1A2C1006050)
  • Ministry of Science and ICT (No. 2021-0-01475, No. NRF-2020R1A2C1006331, 2022R1A2C1006050)

This publication has 14 references indexed in Scilit: