Back to search

NJIT

Experiments with the gap variation of interpolation search for semi uniform distributed alphabetic files

Abstract

dc:description.abstract

<p>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'</p><p>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.</p><p> 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.</p>

Degree

thesis:*
Name thesis:degree_name
Master of Science in Computer Science - (M.S.)
Discipline thesis:degree_discipline
Computer and Information Science

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Bhavsar, Jatin M.
Contributors dc:contributor
  • Yehoshua Perl

Subjects

dc:subject × 3

Identifiers

dc:identifier.*
Repository record dc:identifier
https://digitalcommons.njit.edu/theses/2401

Chain of custody

source
Harvested from
NJIT
Base URL
digitalcommons.njit.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Bhavsar, Jatin M.. Experiments with the gap variation of interpolation search for semi uniform distributed alphabetic files. https://digitalcommons.njit.edu/theses/2401