Coresets for the Nearest-Neighbor Rule
  Given a training set $P$ of labeled points, the nearest-neighbor rule
predicts the class of an unlabeled query point as the label of its closest
point in the set. To improve the time and space complexity of classification, a
natural question is how to reduce the training set without significantly
affecting the accuracy of the nearest-neighbor rule. Nearest-neighbor
condensation deals with finding a subset $R \subseteq P$ such that for every
point $p \in P$, $p$'s nearest-neighbor in $R$ has the same label as $p$. This
relates to the concept of coresets, which can be broadly defined as subsets of
the set, such that an exact result on the coreset corresponds to an approximate
result on the original set. However, the guarantees of a coreset hold for any
query point, and not only for the points of the training set.
  This paper introduces the concept of coresets for nearest-neighbor
classification. We extend existing criteria used for condensation, and prove
sufficient conditions to correctly classify any query point when using these
subsets. Additionally, we prove that finding such subsets of minimum
cardinality is NP-hard, and propose quadratic-time approximation algorithms
with provable upper-bounds on the size of their selected subsets. Moreover, we
show how to improve one of these algorithms to have subquadratic runtime, being
the first of this kind for condensation.
