Analysis of approximate nearest neighbor searching with clustered point sets
Songrit Maneewongvatana, David M. Mount · DIMACS series in discrete mathematics and theoretical computer science · 2002
this paper we study the performance of two other splitting methods, and compare them against the kd-tree splitting method. The first, called slidingmidpoint, is a splitting method that was introduced by Mount and Arya in the ANN library for approximate nearest neighbor searching [30]. This method was introduced into the library in order to better handle highly clustered data sets. We know of no analysis (empirical or theoretical) of this method. This method was designed as a simple technique for addressing one of the most serious flaws in the standard kd-tree splitting method. The flaw is that when the data points are highly clustered in low dimensional subspaces, then the standard kd-tree splitting method may produce highly elongated cells, and these can lead to slow query times. This splitting method starts with a simple midpoint split of the longest side of the cell, but if this split results in either subcell containing no data points, it translates (or "slides") the splitting plane in the direction of the points until hitting the first data point. In Section 3.1 we describe this splitting method and analyze some of its properties. The second splitting method, called minimum-ambiguity, is a query-based technique. The tree is given not only the data points, but also a collection of sample query points, called the training points. The algorithm applies a greedy heuristic to build the tree in an attempt to minimize the expected query time on the training points. We model query processing as the problem of eliminating data points from consideration as the possible candidates for the nearest neighbor. Given a collection of query points, we can model any stage of the nearest neighbor algorithm as a bipartite graph, called the candidate graph, whose vertices correspond t...