Enhancing Multidimensional Tree Structures by Using a Bi-Linear Decomposition

摘要

The k-d tree data structure provides a relatively distribution-independent meansfor satisfying orthogonal range queries on k-dimensional objects in average case time. This time is proportional to the theoretic optimum for any data structure whose storage requirements scale linearly. Given this optimality, much work in the area of distribution-independent near-neighbor algorithms has been directed towards enhancing the k-d tree and its associated search techniques to reduce its search time proportionality constant. This report suggests an enhancement that furthers this end. Important applications include data correlation problems associated with multitarget tracking. In particular, techniques described in this report have been incorporated into the TRC and Real tracking and correlation systems. A k-d tree is a binary in which the set of k-dimensional points may be partitioned at each node according to any of the k coordinates. The discriminating coordinate for each node can be selected to prevent anisotropy in the distribution. This is accomplished by recursively partitioning the set according to the median data point of the projection of the data onto the coordinate axis that has the greatest dispersion. Thus, a node will contain (either implicity or explicity) identification of the discriminating coordinate and pointers to the set of points whose values for the discriminating coordinate are greater than that of the median and to the set of points whose values are less than the median. (kr)