1978/07/01 by Yehoshua Perl, Alon Itai, Haim Avni · 1 citation
Computer Science · Decision Sciences · #Advanced Database Systems and Queries #Algorithms and Data Compression #Data Quality and Management
paper · pdf · doi:10.1145/359545.359557
openalex publication_date 1978/07/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Interpolation search is a method of retrieving a desired record by key in an ordered file by using the value of the key and the statistical distribution of the keys. It is shown that on the average log log N file accesses are required to retrieve a key, assuming that the N keys are uniformly distributed. The number of extra accesses is also estimated and shown to be very low. The same holds if the cumulative distribution function of the keys is known. Computational experiments confirm these results.