The Taub Faculty of Computer Science Events and Talks

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