Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Lower Bounds on Near Neighbor Search via Metric Expansion
event speaker icon
Udi Weider (Microsoft Research)
event date icon
Wednesday, 05.01.2011, 13:20
event location icon
Taub 701 (note unusual room)
We show that the cell probe complexity of performing nearest neighbor (NNS) search on a metric space is tightly related to the expansion of the metric space: Given a metric space we look at the graph obtained by connecting every pair of points within a certain distance r. We then look at various notions of expansion in this graph relating them to the cell probe complexity of NNS for randomized and deterministic, exact and approximate algorithms. These relationships can be used to derive most of the known lower bounds in the well known metric spaces such as l1, l2, l1 by simply computing their expansion, as well as several new ones. Our work essentially reduces the problem of proving cell probe lower bounds of near neighbor search to that of computing the appropriate expansion parameter.

Joint work with Rina Panigrahy and Kunal Talwar