Research on Construction of K-d Tree Based on Euclidean Distance
Traditional k-d tree is constructed according to the order in which data appear, so the balance and depth of the constructed k-d tree are not ideal. To overcome the disadvantages of the construction of traditional k-d tree, this paper proposes a new constructing method based on Euclidean distance so that the construction begins with the center of the data, and every time the points of the nearest distance are used to construct k-d tree, so k-d tree generated in this way is relatively better balanced and has better depth, therefore good searching performance is achieved.
H. F. Ding et al., "Research on Construction of K-d Tree Based on Euclidean Distance", Advanced Materials Research, Vols. 268-270, pp. 994-999, 2011