Nearest neighbor search is the problem of computing the most similar objects to a given query object. Typically objects are represented as vectors in a high-dimensional space. You want to be able to compute similar objects fast even when the database contains millions of objects.

Varieties of the problem

  • Sparse Data vs. Dense Data
  • Systems (standalone systems vs. keyword search systems)
  • Online queries vs. batch
  • Queries vs. all nearest neighbors problem
  • Types of similarity

What’s new