1. Standard Vs Uniform Binary Search and Their Variants in Learned Static Indexing: The Case of the Searching on Sorted Data Benchmarking Software Platform
- Author
-
Domenico Amato, Giosué Lo Bosco, Raffaele Giancarlo, Domenico Amato, Giosue Lo Bosco, and Raffaele Giancarlo
- Subjects
I.2 ,FOS: Computer and information sciences ,Computer Science - Machine Learning ,learned index structures ,H.2 ,Databases (cs.DB) ,search on sorted data platform ,Computer Science - Information Retrieval ,Machine Learning (cs.LG) ,E.1 ,Computer Science - Databases ,binary search variants ,Computer Science - Data Structures and Algorithms ,Data Structures and Algorithms (cs.DS) ,algorithms with prediction ,Software ,Information Retrieval (cs.IR) - Abstract
Learned Indexes are a novel approach to search in a sorted table. A model is used to predict an interval in which to search into and a Binary Search routine is used to finalize the search. They are quite effective. For the final stage, usually, the lower_bound routine of the Standard C++ library is used, although this is more of a natural choice rather than a requirement. However, recent studies, that do not use Machine Learning predictions, indicate that other implementations of Binary Search or variants, namely k-ary Search, are better suited to take advantage of the features offered by modern computer architectures. With the use of the Searching on Sorted Sets SOSD Learned Indexing benchmarking software, we investigate how to choose a Search routine for the final stage of searching in a Learned Index. Our results provide indications that better choices than the lower_bound routine can be made. We also highlight how such a choice may be dependent on the computer architecture that is to be used. Overall, our findings provide new and much-needed guidelines for the selection of the Search routine within the Learned Indexing framework., Comment: arXiv admin note: substantial text overlap with arXiv:2107.09480
- Published
- 2022
- Full Text
- View/download PDF