6533b82bfe1ef96bd128d616

RESEARCH PRODUCT

Standard Vs Uniform Binary Search and Their Variants in Learned Static Indexing: The Case of the Searching on Sorted Data Benchmarking Software Platform

Domenico AmatoGiosué Lo BoscoRaffaele Giancarlo

subject

I.2FOS: Computer and information sciencesComputer Science - Machine Learninglearned index structuresH.2Databases (cs.DB)search on sorted data platformComputer Science - Information RetrievalMachine Learning (cs.LG)E.1; I.2; H.2Computer Science - Databasesbinary search variantsComputer Science - Data Structures and AlgorithmsData Structures and Algorithms (cs.DS)E.1algorithms with predictionSoftwareInformation Retrieval (cs.IR)

description

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.

yearjournalcountryeditionlanguage
2023-09-06
https://dx.doi.org/10.48550/arxiv.2201.01554