Multidimensional Binary Search Trees in Database Applications
Jon Louis Bentley · IEEE Transactions on Software Engineering · 1979
The multidimensional binary search tree (abbreviated k-d tree) is a data structure for storing multikey records. This structure has been used to solve a number of "geometric" problems in statistics and data analysis. The purposes of this paper are to cast k-d trees in a database framework, to collect the results on k-d trees that have appeared since the structure was introduced, and to show how the basic data structure can be modified to facilitate implementation in large (and very large) databases.
Cited by 410 works. doi:10.1109/tse.1979.234200
Authors
References
- The Art of Computer Programming
- Multidimensional binary search trees used for associative searching
- An Algorithm for Finding Best Matches in Logarithmic Expected Time
- The Art of Computer Programming, Vol. 3: Sorting and Searching
- Partial-Match Retrieval Algorithms
- Decomposable searching problems
- Database design
- Worst-case analysis for region and partial region searches in multidimensional binary search trees and balanced quad trees
- Topics in Computational Geometry
- Fast Algorithms for Constructing Minimal Spanning Trees in Coordinate Spaces