דלג לתוכן (מקש קיצור 's')
Logo of Technion
Logo of CS Department
אירועים

אירועים

Theory Seminar: Lower Bounds on Near Neighbor Search via Metric Expansion
event speaker icon
Udi Weider (Microsoft Research)
event date icon
יום רביעי, 5.1.2011, 13:20
event location icon
טאוב 701
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
[בחזרה לאינדקס האירועים]