An Empirical Study of Segmented Linear Regression Search in LevelDB
Open Access
- 17 February 2023
- journal article
- research article
- Published by MDPI AG in Electronics
- Vol. 12 (4) , 1018
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.Keywords
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:
- Benchmarking learned indexesProceedings of the VLDB Endowment, 2020
- SIndex2020
- RadixSpline2020
- ALEX: An Updatable Adaptive Learned Index2020
- The PGM-indexProceedings of the VLDB Endowment, 2020
- Function Interpolation for Learned Index Structures2020
- FITing-Tree2019
- Wormhole2019
- The Case for Learned Index Structures2018
- PebblesDB2017