Standard Vs Uniform Binary Search and Their Variants in Learned Static Indexing: The Case of the Searching on Sorted Data Benchmarking Software Platform
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.
Code (1)
Tasks
BenchmarkingSimilar Papers 제목 키워드 기반
Simplified Long Short-term Memory Recurrent Neural Networks: part I
We present five variants of the standard Long Short-term Memory (LSTM) recurrent neural networks by uniformly reducing blocks of adaptive parameters in the gating mechanisms. For simplicity, we refer to these models as L…
2D moment invariants from the point of view of the classical invariant theory
Invariants allow to classify images up to the action of a group of transformations. In this paper we introduce notions of the algebras of simultaneous polynomial and rational 2D moment invariants and prove that they are …
Inference on Individual Treatment Effects in Nonseparable Triangular Models
In nonseparable triangular models with a binary endogenous treatment and a binary instrumental variable, Vuong and Xu (2017) established identification results for individual treatment effects (ITEs) under the rank invar…
validMimeLens: Position-Agnostic Content-Type Detection for Binary Fragments
File-type classification underlies many workflows like malware triage, forensic carving, packet inspection, and storage indexing. Learned systems such as Google's Magika assume whole-file access at a known offset, so the…
Dynamics of Virus and Immune Response in Multi-Epitope Network
The host immune response can often efficiently suppress a virus infection, which may lead to selection for immune-resistant viral variants within the host. For example, during HIV infection, an array of CTL immune respon…