Learned Indexes use a model to restrict the search of a sorted table to a smaller interval. Typically, a final binary search is done using the lower_bound routine of the Standard C++ library. Recent studies have shown that on current processors other search approaches (such as k-ary search) can be more efficient in some applications. Using the SOSD learned indexing benchmarking software, we extend these results to show that k-ary search is indeed a better choice when using learned indexes. We highlight how such a choice may be dependent on the computer architecture used, for example, Intel I7 or Apple M1, and provide guidelines for the selection of the Search routine within the learned indexing framework.

Domenico Amato, Giosue Lo Bosco, Raffaele Giancarlo (2023). Standard versus uniform binary search and their variants in learned static indexing: The case of the searching on sorted data benchmarking software platform. SOFTWARE-PRACTICE & EXPERIENCE, 53(2), 318-346 [10.1002/spe.3150].

Standard versus uniform binary search and their variants in learned static indexing: The case of the searching on sorted data benchmarking software platform

Domenico Amato;Giosue Lo Bosco
;
Raffaele Giancarlo
2023-09-06

Abstract

Learned Indexes use a model to restrict the search of a sorted table to a smaller interval. Typically, a final binary search is done using the lower_bound routine of the Standard C++ library. Recent studies have shown that on current processors other search approaches (such as k-ary search) can be more efficient in some applications. Using the SOSD learned indexing benchmarking software, we extend these results to show that k-ary search is indeed a better choice when using learned indexes. We highlight how such a choice may be dependent on the computer architecture used, for example, Intel I7 or Apple M1, and provide guidelines for the selection of the Search routine within the learned indexing framework.
https://onlinelibrary.wiley.com/doi/10.1002/spe.3150
Domenico Amato, Giosue Lo Bosco, Raffaele Giancarlo (2023). Standard versus uniform binary search and their variants in learned static indexing: The case of the searching on sorted data benchmarking software platform. SOFTWARE-PRACTICE & EXPERIENCE, 53(2), 318-346 [10.1002/spe.3150].
File in questo prodotto:
File Dimensione Formato  
Softw _Pract_Exp_2022_ Amato_Standard_versus_uniform_binary_search_and_their_variants_in_learned_static_indexing.pdf

accesso aperto

Tipologia: Versione Editoriale
Dimensione 2.4 MB
Formato Adobe PDF
2.4 MB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10447/578350
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact