Back to search

NJIT

Interpolation search for alphabetic tables

Abstract

dc:description.abstract

<p>One of the fastest search techniques for uniformly distributed sorted numerical tables is interpolation search. This divide and conquer technique accesses the most probable key rather than the middle key as in binary search and continues to search similarly the appropriate part of the table . In the previous work we proved a lg lg n average number of accesses for interpolation search.</p><p>The inefficiency of interpolation search for an alphabetic table is demonstrated by Burton and Lewis and a robust variation suggested by them to improve the efficiency. This inefficiency is expected since such tables are usually far from uniform distribution. However for non-uniformly distributed tables for which the cumulative distribution function F is known, applying F to the keys yields uniform distribution for which interpolation search is very fast.</p><p>In arithmetic coding a string of characters is mapped into the [0,1] interval according to the probabilities of its characters. We found that this transformation, designed for data compression, is actually the cummulative distribution function F for alphabetic tables. Experiments confirm that interpolation search on alphabetic tables, applying arithmetic coding to the character -strings in a sophisticated way, show a performance very close to lg lg n accesses. Hence we design a new fast search technique for alphabetic tables.</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
  • Gabriel, Loizos
Contributors dc:contributor
  • Yun Q. Shi

Subjects

dc:subject × 4

Identifiers

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

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

Gabriel, Loizos. Interpolation search for alphabetic tables. https://digitalcommons.njit.edu/theses/2755