Further results on interpolation searching of databases
Z.J. Li, Harry K. T. Wong · eScholarship (California Digital Library) · 1986
This paper extends known results of the Interpolation Search Algorithm on ordered tables in three ways.First, it examines the effect of hatching the search queries.Second, it applies the basically main-memory algorithm to a more typical database environment, i.e. a blocked secondary memory.Third, it examines a hybrid algorithm to remedy the worst case behavior of the pure Interpolation Search in the event of non-uniform distribution of the ordered file while retaining the average complexity.Algorithms, analytic expressions and experiment results of these extensions are given and described.Analytic expressions of these algorithms are validated by the experiments.