Large 00004

Perspectives on Nearest Neighbor Search in High-Dimensional Spaces

Alexandr Andoni

Recorded 13 June 2012 in Lausanne, Vaud, Switzerland

Event: SuRI - I&C - Summer Research Institute

Abstract

Nearest neighbor search in high-dimensional spaces is a ubiquitous problem in searching and analyzing massive data sets. In this problem, the goal is to preprocess a set of objects (such as images), so that later, given a new query object, one can efficiently return the object most similar to the query. This problem is of key importance in several areas, including machine learning, information retrieval, image/video/music clustering, and others. For instance, it forms the basis of a widely used classification method in machine learning: to label a new object, just find a similar but already-labeled object. Nearest neighbor search also serves as a primitive for other computational problems such as closest pair, minimum spanning tree, or variants of clustering.

In this talk, I will survey the state-of-the-art for the nearest neighbor search. I will give a flavor of the main algorithms and techniques involved, both some classical and more recent ones. Along the way, I will highlight the current challenges in the area.

Watched 9053 times.

 Watch