A Parallel Architecture for k-d Trees

Abstract

The authors describe a special purpose computer architecture for the parallel processing of queries, including associative searches, in a dynamic file. The architecture is a highly-parallel network of small processors of two types connected in a full binary tree network. Records are stored in the leaves of the tree; each leaf processor is responsible for records occurring within a rectangular solid part of the space. Queries and record updates are fed into the root of the tree. Internal nodes selectively direct each query and update to leaves so that each leaf sees only the information geometrically close to the records for which it is responsible. File updates cause a reorganization of the tree, which is accomplished in a manner that can accommodate either incremental or massive changes. The architecture can be viewed as a hardware implementation of Bentley's k-d trees. The design is extensible and well-suited to implementation in VLSI. Keywords: Algorithms, Multiple target tracking. Author.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 01, 1988
Accession Number
ADA201087

Entities

People

  • Donald F. Stanat
  • Geoffrey A. Frank

Organizations

  • University of North Carolina at Chapel Hill

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Computations
  • Computer Architecture
  • Computers
  • Computing System Architectures
  • Databases
  • Lymphocytes
  • Machines
  • Multitarget Tracking
  • Organizational Realignment
  • Parallel Computing
  • Parallel Processing
  • Parallel Processors
  • Target Tracking
  • Trees (Data Structures)
  • Two Dimensional

Readers

  • Computer Vision.
  • Forest Ecology
  • Parallel and Distributed Computing.

Technology Areas

  • Space