A Parallel Architecture for k-d Trees
Geoffrey A. Frank, Donald F. Stanat · 1988
We 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.-K< 4. 1.