Premium
Success rate of interpolation in subsegment prediction
Author(s) -
Wright William E.,
Jeyaratnam Sakthivel
Publication year - 1993
Publication title -
software: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.437
H-Index - 70
eISSN - 1097-024X
pISSN - 0038-0644
DOI - 10.1002/spe.4380230303
Subject(s) - computer science , key (lock) , interpolation (computer graphics) , file size , computer network , operating system , frame (networking)
We consider the accuracy of linear interpolation in predicting which subsegment contains a random key, given that the key is contained in a particular segment consisting of a fixed number of subsegments. We assume that keys are stored in a file in sorted order, that the file is divided into fixed‐size segments, and that the first key in the segment containing the desired key is known, as is the first key of the next segment. We present empirical results for real files in which keys are social security numbers, names and telephone numbers, and for files of keys generated randomly from the uniform and from the exponential distributions. We present a theoretical analysis of the average success rate for the case in which keys are uniformly distributed. We show that the success rate depends on the number of subsegments in a segment, the size of a subsegment, and the distribution of keys, and that it is much higher than for random guessing. We describe practical applications in which this technique can be efficiently used.