Multidimensional Binary Search Trees in Database Applications.

摘要

The multidimensional binary search tree (abbreviated k-d tree) is a data structure for storing multi-key records. This structure has been used to solve a number of problems in geometric data bases arising 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 which 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. (Author)