Randomized binary search technique

ABSTRACT

A mathematical model is developed for the mean and variance of the number of trials to recover a given document in a randomly received list of files. The search method described is binary in nature and offers new potential for information retrieval systems.

REFERENCES

• 1: Edward H. Sussenguth, Jr., Use of tree structures for processing files, Communications of the ACM, v.6 n.5, p.272-279, May 1963 [doi>10.1145/366552.366600]
• 2: Harry A. Clampett, Jr., Randomized binary searching with tree structures, Communications of the ACM, v.7 n.3, p.163-165, March 1964 [doi>10.1145/363958.363987]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Graph and tree search strategies

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process

General Terms:
Design, Management, Theory

Keywords:
binary pattern, file examination, graph theory, information retrieval, mathematical model, partitioning, probabilistic method, random sequencing, search techniques, tree structures