Two Papers on Range Searching: A Survey of Algorithms and Data Structures for Range Searching. Efficient Worst-Case Data Structures for Range Searching.

Abstract

This report contains two independent papers on range searching. A range search retrieves from a file all records which conjunctively satisfy a set of range requirements for the keys; that is, each key must lie in some specified range. Range searching arises in many applications, such as data base management and statistical computing. The first paper in this report, 'A survey of algorithms and data structures for range searching' by J. L. Bentley and J. H. Friedman, describes the known 'logical structures' which can be used for range searching and then discusses the implementation of those structures in different storage media. This paper is slanted towards the practitioner. The second paper, 'Efficient worst-case data structures for range searching' by J. L. Bentley and H. A. Maurer, is more theoretical. Two new classes of data structures are proposed for range searching, establishing bounds on the asymptotic complexity of the problem. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Aug 01, 1978
Accession Number
ADA060584

Entities

People

  • H. A. Maurer
  • Jerome H. Friedman
  • Jon Louis Bentley

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Materials and Manufacturing Processes
  • Weapons Technologies

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Cell Size
  • Computations
  • Computer Programming
  • Computer Programs
  • Computer Science
  • Computers
  • Data Analysis
  • Databases
  • Grids
  • Information Processing
  • Linear Accelerators
  • Magnetic Tape
  • Mathematical Analysis
  • Trees (Data Structures)
  • Two Dimensional

Fields of Study

  • Computer science

Readers

  • Adaptive Control and Estimation with Uncertainty in Dynamic Systems.
  • Computer Science.
  • Theoretical Analysis.