Access Restriction

Author Avni, Haim ♦ Itai, Alon ♦ Perl, Yehoshua
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Retrieval ♦ Binary search ♦ Average number of accesses ♦ Uniform distribution ♦ Searching ♦ Database ♦ Interpolation search
Abstract 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 logN 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.
Description Affiliation: Israel Institute of Technology, Haifa, Israel (Itai, Alon) || Bar-Ilan Univ., Ramat Gan, Israel (Perl, Yehoshua) || The Weizmann Institute of Science, Rehovot, Israel (Avni, Haim)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 21
Issue Number 7
Page Count 4
Starting Page 550
Ending Page 553

Open content in new tab

   Open content in new tab
Source: ACM Digital Library