Nearest Neighbor Search with Graphs

Sanjiv Kumar
Google Research

Nearest neighbor search in massive databases is a crucial component of large-scale multimedia search. The first part of the talk will focus on the question how difficult and meaningful is it to do nearest neighbor search in a given data set. In particular, I will show how one can measure the relevance of nearest neighbor search in an application with respect to data dimensionality, sparsity, distance metric and database size. Next, I will discuss nearest neighbor search when data lives on a manifold, i.e., the given distance metric only applies in local neighborhoods. This leads to manipulating a large graph, which is solved approximately using Anchor Graphs. Preliminary experimental results on real-world data verify the effectiveness of the proposed method.

Back to Large Scale Multimedia Search