• Calendar

November 1, Tuesday
10:30 – 12:30

In the nearest neighbor search problem, we are required to preprocess a database X in order to quickly answer queries of the following type: Given a new item y, find the (approximate) closest item in X. In this talk I'll present an algorithm for this problem when the distances between the items in X form a "low dimensional" metric. Another application of our technique is distributed and linear storage representations of the pairwise distances in X. The main technical tool being used is a fast algorithm for constructing hierarchical nets in low dimensional finite metric spaces

Joint work with S. Har-Peled

BIO:

Manor Mendel teaches computer science at the Open University of Israel. His main research interests focus on geometric methods in the design of approximation algorithms, with emphasis on the theory of embeddings of finite metric spaces.