We revisit the classical algorithms for searching over sorted sets to introduce an algorithm refinement, called Adaptive search, that combines the good features of Interpolation search and those of Binary search. W.r.t. Interpolation search, only a constant number of extra comparisons is introduced. Yet, under diverse input data distributions our algorithm shows costs comparable to that of Interpolation search, i.e., O(log log n) while the worst-case cost is always in O(log n), as with Binary search. On benchmarks drawn from large datasets, both synthetic and real-life, Adaptive searchscores better times and lesser memory accesses even than Santoro and Sidney's Interpolation-Binary search.

Adaptive Search over Sorted Sets

BONASERA, BIAGIO
Primo
Membro del Collaboration Group
;
FERRARA, EMILIO
Secondo
Membro del Collaboration Group
;
FIUMARA, Giacomo
Membro del Collaboration Group
;
PROVETTI, Alessandro
Ultimo
Membro del Collaboration Group
2015-01-01

Abstract

We revisit the classical algorithms for searching over sorted sets to introduce an algorithm refinement, called Adaptive search, that combines the good features of Interpolation search and those of Binary search. W.r.t. Interpolation search, only a constant number of extra comparisons is introduced. Yet, under diverse input data distributions our algorithm shows costs comparable to that of Interpolation search, i.e., O(log log n) while the worst-case cost is always in O(log n), as with Binary search. On benchmarks drawn from large datasets, both synthetic and real-life, Adaptive searchscores better times and lesser memory accesses even than Santoro and Sidney's Interpolation-Binary search.
2015
File in questo prodotto:
File Dimensione Formato  
adaptive-search-JDA-sub2.pdf

accesso aperto

Tipologia: Documento in Pre-print (manoscritto inviato all'editore, precedente alla peer review)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 107.59 kB
Formato Adobe PDF
107.59 kB Adobe PDF Visualizza/Apri
bonasera-adaptive_search-JDA15.pdf

accesso aperto

Tipologia: Versione Editoriale (PDF)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 210.72 kB
Formato Adobe PDF
210.72 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

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/11570/2431643
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 5
social impact