05/03/2012: Advances in High-Dimensional Nearest Neighbor Searching

Advances in High-Dimensional Nearest Neighbor Searching

March 5, 2012, 16:30 - 18:00, HG G 19.1, ETH Zurich

Stavros Gerakaris
University of Edinburgh, UK

Over the last decades vast amount of data has become available. A fundamental computational problem for dealing with high-dimensional data is Nearest Neighbor Searching (NNS). In this talk we present several methods for NNS developed by the Database and the Computational Geometry community as well. These indexes, including FLANN, ANN, LSH and iDistance, are state-of-the-art in the field and efficiently treat high-dimensional data.

We give emphasis in the theoretical aspects of the problem, in order to understand why these methods work. Finally, by comparing different approaches we witness basic tools that these communities share in common, when dealing with high-dimensional data, and we discuss the ways in which complementary approaches can learn from each other and  facilitate further advances.