Multidimensional Binary Search Trees in Database Applications
- 1 July 1979
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Software Engineering
- Vol. SE-5 (4) , 333-340
- https://doi.org/10.1109/tse.1979.234200
Abstract
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.Keywords
This publication has 8 references indexed in Scilit:
- Decomposable searching problemsInformation Processing Letters, 1979
- Fast Algorithms for Constructing Minimal Spanning Trees in Coordinate SpacesIEEE Transactions on Computers, 1978
- An Algorithm for Finding Best Matches in Logarithmic Expected TimeACM Transactions on Mathematical Software, 1977
- Worst-case analysis for region and partial region searches in multidimensional binary search trees and balanced quad treesActa Informatica, 1977
- Partial-Match Retrieval AlgorithmsSIAM Journal on Computing, 1976
- Heuristics for partial-match retrieval data base designInformation Processing Letters, 1976
- Multidimensional binary search trees used for associative searchingCommunications of the ACM, 1975
- Analysis of range searches in quad treesInformation Processing Letters, 1975