Speaker: Sariel Har-Peled (UIUC)
Title:   Down the Rabbit Hole: Robust Proximity Search in Sublinear Space

Abstract:
---------
For a set of n points in R^d, and parameters k and µ, we present a data
structure that answers (1+µ)-approximate k nearest neighbor queries in
logarithmic time. Surprisingly, the space used by the data-structure
is (roughly) O(n/k); that is, the space used is sublinear in the input
size if k is sufficiently large. Our approach provides a novel way to
summarize geometric data, such that meaningful proximity queries on
the data can be carried out using this sketch.

Joint work with Nirman Kumar.

The paper is available from here:
http://valis.cs.uiuc.edu/~sariel/papers/11/kann/