Tree structures for high dimensionality nearest neighbor searching

摘要

A nearest neighbor searching algorithm which is an extension of the multidimensional binary tree (k-d tree) for high dimensional spaces is discussed. A model of its behavior, which is applicable under restricted conditions, shows that the search time required is bounded by 0(log2 N)α, where N is the number of records and α is a system-dependent parameter. Experiments with a document collection show that the model provides a reasonable guide to performance, and that some savings over a sequential search can be achieved in this type of application. A probabilistic version of the algorithm is presented which provides significantly faster searching with little degradation in retrieval quality.