Boundary-Sensitive Approach for Approximate Nearest-Neighbor Classification

The problem of nearest-neighbor classification is a fundamental technique in machine-learning. Given a training set P of n labeled points in ?^d, and an approximation parameter 0 < ? ? 1/2, any unlabeled query point should be classified with the class of any of its ?-approximate nearest-neighbors in P. Answering these queries efficiently has been the focus of extensive research, proposing techniques that are mainly tailored towards resolving the more general problem of ?-approximate nearest-neighbor search. While the latest can only hope to provide query time and space complexities dependent on n, the problem of nearest-neighbor classification accepts other parameters more suitable to its analysis. Such is the number k_? of ?-border points, which describes the complexity of boundaries between sets of points of different classes. This paper presents a new data structure called Chromatic AVD. This is the first approach for ?-approximate nearest-neighbor classification whose space and query time complexities are only dependent on ?, k_? and d, while being independent on both n and ?, the spread of P