Worst-Case Analyses of Self-Organizing Sequential Search Heuristics.

Abstract

The performance of sequential search can be enhanced by the use of heuristics that move elements closer to the front of the list as they are found. Previous analyses have characterized the performance of such heuristics probabilitically. In this paper we show that the heuristics can also be analyzed in the worst-case sense, and that the relative merit of the heuristics under this analysis is different than in the probabilistic analyses. Simulations show that the relative merit of the heuristics on real data is closer to that of the new worst-case analyses rather than that of the previous probabilistic analyses. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Mar 28, 1983
Accession Number
ADA129665

Entities

People

  • Catherine Cole Mcgeoch
  • Jon Louis Bentley

Organizations

  • Carnegie Mellon University

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Computer Programming
  • Computer Programs
  • Computer Science
  • Computers
  • Frequency
  • Inequalities
  • Lists (Data Structures)
  • Markov Chains
  • Probabilistic Models
  • Probability
  • Probability Distributions
  • Self Organizing Systems
  • Sequences
  • Simulations
  • Simulators
  • United States

Fields of Study

  • Computer science

Readers

  • Adaptive Control and Estimation with Uncertainty in Dynamic Systems.
  • Operations Research