Earticle

초록

영어

Binary search is an efficient algorithm for finding an item from a sorted data. Although binary search is very powerful, sometimes the process of binary search is very inefficient to find items that are next to the starting or ending items. To overcome this problem, a novel approach called learned index has been proposed recently. The key idea of the learned index is replacing an index construction with a model training and a lookup via index as an inference via model. In this paper, as a case study of the learned index, we design a new search algorithm, called Segmented Linear Regression (SLR) based search. It employs SLR to estimate the approximate location of a given key and to decrease the error distance during searching. We have conducted experiments with two real-world datasets, OpenStreetMap and Twitter User data. Evaluation results show that our proposal is about 1.38x faster than the binary search.

목차

Abstract
1. Introduction
2. Proposal
2.1. Binary Search
2.2. SLR based Search
3. Evaluation
4. Related Work
5. Conclusions
Acknowledgement
References

저자

• Ramadhan Agung Rahmat [ Department of Software Dankook University ]
• Jongmoo Choi [ Department of Software Dankook University ] Corresponding author

참고문헌