Parallel Interpolation Search.

Abstract

This paper concerns the problem of searching, with p parallel processors, for a given key in a random ordered table of size n. We propose a parallel interpolation algorithm which we show has expected time cost < or equal log(1 + log (n)/log(p) + 0(1) and we prove this algorithm has optimal expected time cost within a constant additive term. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Mar 01, 1982
Accession Number
ADA114611

Entities

People

  • John Reif

Organizations

  • Harvard University

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Additives (Chemicals)
  • Algorithms
  • Binomials
  • Computations
  • Computer Science
  • Distribution Functions
  • Interpolation
  • Iterations
  • Military Research
  • New York
  • Normal Distribution
  • Parallel Processors
  • Probability
  • Random Variables
  • Stochastic Processes
  • Universities

Fields of Study

  • Computer science
  • Mathematics

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Approximation Theory.