A paper by Chancellor’s Professor of Computer Science David Eppstein, “Finding Relevant Points for Nearest-Neighbor Classification,” has won the best paper award of the 2022 SIAM Symposium on Simplicity in Algorithms (SOSA22), to be held in a hybrid online and in-person format in Virginia in January 2022, jointly with several other SIAM conferences.

The Symposium on Simplicity in Algorithms is an annual conference, established in 2018 and sponsored by the Society for Industrial and Applied Mathematics (SIAM), “dedicated to advancing algorithms research by promoting simplicity and elegance in the design and analysis of algorithms.”

Eppstein’s paper concerns nearest-neighbor classification, a widely used method for predicting the properties of data points using a “training set” of points whose properties are known, by predicting that each new point will behave the same as its closest neighbor in the training set. The paper describes a new polynomial-time algorithm for simplifying the training set, by eliminating points that do not contribute to the boundary between regions of space with different predictions. In keeping with the focus of the conference, the new algorithm is based on a simple combination of two subroutines, for minimum spanning trees and convex hull vertices, both of which in turn have simple known algorithms.

A preprint version of the paper is available online.