Jon Louis Bentley
Abstract
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 efficient 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 is theoretical. It is felt, however, that k-d trees could be quite useful in many applications, and examples of potential uses are given.
- 1 Friedman, J.H., Bentley, J.L., and Finkel, R.A. An algorithm for finding best matches in logarithmic time. Stanford CS Rep. 75--482. Google Scholar
Digital Library
- 2 Blum, M., Floyd, R.W., Pratt, V., Rivest, R.L., and Tarjan, R.E. Time bounds for selection. Stanford CS Rep. 73-349.Google Scholar
- 3 Finkel, R.A., and Bentley, J.L. "Quad trees: a data structure for retrieval on composite key." Acta lnformatica 4, 1 (1974), 1-9.Google ScholarDigital Library
- 4 Knuth, D.E. The Art of Computer Programming, Vol. 1: Fundamental Algorithms. Addison-Wesley, Reading, Mass., 1969. Google ScholarDigital Library
- 5 Knuth, D.E. The Art of Computer Programmhtg, Vol. 1li: Sorting and Searching. Addison-Wesley, Reading, Mass., 1973. Google ScholarDigital Library
- 6 McCreight, E. Computer Science 144A midterm examination, spring quarter, 1973. Stanford University.Google Scholar
- 7 Rivest, R.L. Analysis of associative retrieval algorithms. Stanford CS Rep. 74--415.Google Scholar
Index Terms
- Multidimensional binary search trees used for associative searching
Recommendations
Generalizing a Theorem of Wilber on Rotations in Binary Search Trees to Encompass Unordered Binary Trees
Wilber’s logarithmic lower bound, concerning off-line binary search tree access costs, is generalized to encompass binary trees that are not constrained to satisfy the search tree property. Rotation operations in this extended model can be preceded by ...
An immediate approach to balancing nodes in binary search trees
We present an immediate approach in hoping to bridge the gap between the difficulties of learning ordinary Binary Search Trees (henceforth BST) and their height-balanced variants in the typical data structures class. For each node in the tree, instead ...
Dynamic Binary Search Trees
ACM '78: Proceedings of the 1978 annual conferenceThis paper compares the performance of many algorithms designed to maintain balance in binary search trees. The algorithms are rated primarily in terms of execution speed, although weighted path length is also included. The investigation includes ...
Comments