The New Jersey Institute of Technology's
Electronic Theses & Dissertations Project

Title:	Experiments with the gap variation of interpolation search for semi uniform distributed alphabetic files
Author:	Bhavsar, Jatin M.
View Online:	njit-etd1991-082 ([ii], 114 pages ~ 1.8 MB pdf)
Department:	Department of Computer and Information Science
Degree:	Master of Science
Program:	Computer Science
Document Type:	Thesis
Advisory Committee:	Perl, Yehoshua (Committee chair)
Date:	1991-05
Keywords:	Computer files Data compression (Computer science)
Availability:	Unrestricted
Abstract:	There are various techniques for searching a data from a data base. One of them is interpolation search. It works on uniformly distributed and sorted numerical tables and considered to be one of the fastest methods. On an average this method takes 'lg lg n' Burton and Lewis [BL] shows the inefficiency of interpolation sarch for an alphabetic table whose distribution is not known or non-uniform. They introduce GAP variations of interpolation search to compare the inefficiency. However another approach to a non-uniform is to apply the cumulative distribution function F which transfer a non-uniform distribution to uniform one, for which interpolation search is the best. In Arithmetic Coding a string of characters is mapped into the [0,1) interval according to the probabilities of its characters using arithmetic code. We found that this transformation, designed for data compression, is actually the cumulative distritution funciton F for alphabetic tables. However the tables needed for applying Arithmetic Coding require too much memory and only an approximated transformation using only few tables can be applied. This transformation gave a semi-uniform distribution and interpolation search gave higher results than 'lg lg n'. Applying then the GAP variations improved the results where, the optimum close to 'lg lg n' accesses was obtained for the accelerated GAP variation for GAP = 2 rather than √n used in [BL]. An experimental analysis show GAP = 2 to be the best function for uniformly distributed files. We analyzed the regular GAP =2 theoretically to support the experimental result.