Approximate nearest neighbor search in high dimensions – Piotr Indyk – ICM2018

Mathematical Aspects of Computer Science
Invited Lecture 14.7
Approximate nearest neighbor search in high dimensions
Piotr Indyk

Abstract: The nearest neighbor problem is defined as follows: Given a set P of n points in some metric space (X,𝖣), build a data structure that, given any point q, returns a point in P that is closest to q (its “nearest neighbor” in P). The data structure stores additional information about the set P, which is then used to find the nearest neighbor without computing all distances between q and P. The problem has a wide range of applications in machine learning, computer vision, databases and other fields.
To reduce the time needed to find nearest neighbors and the amount of memory used by the data structure, one can formulate the ‘approximate’ nearest neighbor problem, where the the goal is to return any point p' ∈ P such that the distance from q to p' is at most c ⋅ min_{p ∈ P} 𝖣(q,p), for some c ≥ 1. Over the last two decades many efficient solutions to this problem were developed. In this article we survey these developments, as well as their connections to questions in geometric functional analysis and combinatorial geometry.

© International Congress of Mathematicians – ICM
www.icm2018.org  
 
Os direitos sobre todo o material deste canal pertencem ao Instituto de Matemática Pura e Aplicada, sendo vedada a utilização total ou parcial do conteúdo sem autorização prévia e por escrito do referido titular, salvo nas hipóteses previstas na legislação vigente.

The rights over all the material in this channel belong to the Instituto de Matemática Pura e Aplicada, and it is forbidden to use all or part of it without prior written authorization from the above mentioned holder, except in the cases prescribed in the current legislation.