REFINEMENTS TO NEAREST-NEIGHBOR SEARCHING IN K-DIMENSIONAL TREES
REFINEMENTS TO NEAREST-NEIGHBOR SEARCHING IN K-DIMENSIONAL TREES
复制标题
DOI：
10.1007/bf01759061
复制
发表时间：
1991-01-01
期刊：
影响因子：
1.1
通讯作者：
SPROULL, RF
中科院分区：
文献类型：
--
作者：
SPROULL, RF
本文给出了一个由Friedman等人提出的搜索k维树以寻找最近邻居的算法的简化和推广。[3]。如果使用L2(欧几里得范数)来测量记录之间的距离，则该算法用来确定搜索空间界限的数据结构可以简化为单个数字。此外，由于L2中的距离测量是旋转不变的，该算法可以被推广到允许分区平面具有任意方向，而不是像在原始算法中那样坚持它垂直于坐标轴。当建立k维树时，可以从要划分的记录的协方差矩阵的主特征向量中找到该平面。这些技术和其他技术产生了为特定应用定制的k维树的变体。假设k维树保证最近邻查询在对数预期时间内完成是错误的。对于小k，除了微小的树，所有的树都观察到对数行为。然而，对于较大的k，只有在记录数量极大的情况下才能实现对数行为。对于k=16，搜索包含76,000条记录的k维树几乎检查每条记录。
This note presents a simplification and generalization of an algorithm for searching k-dimensional trees for nearest neighbors reported by Friedman et al. [3]. If the distance between records is measured using L2, the Euclidean norm, the data structure used by the algorithm to determine the bounds of the search space can be simplified to a single number. Moreover, because distance measurements in L2 are rotationally invariant, the algorithm can be generalized to allow a partition plane to have an arbitrary orientation, rather than insisting that it be perpendicular to a coordinate axis, as in the original algorithm. When a k-dimensional tree is built, this plane can be found from the principal eigenvector of the covariance matrix of the records to be partitioned. These techniques and others yield variants of k-dimensional trees customized for specific applications.It is wrong to assume that k-dimensional trees guarantee that a nearest-neighbor query completes in logarithmic expected time. For small k, logarithmic behavior is observed on all but tiny trees. However, for larger k, logarithmic behavior is achievable only with extremely large numbers of records. For k = 16, a search of a k-dimensional tree of 76,000 records examines almost every record.