Multidimensional Binary Search Trees Used for Associative Searching

This paper develops the multidimensional binary
search tree (or k-d tree, where k is the dimensionality 
of the search space) as a data structure for storage of
information to be retrieved by associative searches. 
The k-d tree is defined and examples are given. It
is shown to be quite in its storage requirements. 
 A significant advantage of this structure is that a single
data structure can handle many types of queries 
very efficiently.  Various utility algorithms are developed;
their proven average running times in an 
n record file are: insertion, O (log n); deletion of
the root, O (n^(k-1)/k); deletion of a random node, 
O (log n); and optimization (guarantees logarithmic performance
of searches), O (n log n).  Search algorithms 
are given for partial match queries with t keys specified
[proven maximum running time of O (n^(k-t)/k)] 
and for nearest neighbor queries [empirically observed average
running time of O (log n).]  These performances 
far surpass the best currently known algorithms for
these tasks.  An algorithm is presented to handle 
any general intersection query. The main focus of this
paper theoretical.  It is felt, however, that 
k-d trees could be quite useful in many applications,
and examples of potential uses are given.

CACM September, 1975

Bently, J. L.

associative retrieval, binary search trees, key,
attribute, information retrieval system, nearest 
neighbor queries, partial match queries, intersection
queries, binary tree insertion

3.63 3.70 3.74 4.49

CA750902 JB January 6, 1978  3:22 PM

2722	5	2722
2722	5	2722
2722	5	2722