Speaker:  Allan Borodin
Affiliation:  Department of Computer Science, University of Toronto
Date:  9/23/99 Thursday
Time & Location - 4:15 PM, 101 Phillips
Title:  Lower Bounds for High Dimensional Nearest Neighbor Search and Related Problems

The ``curse of dimensionality'' describes the phenomenon whereby (in spite of extensive and continuing research) for various geometric search problems we only have algorithms with performance that grows exponentially (in some sense). Recent results show that it is possible to avoid the curse of dimensionality for the approximate nearest neighbor search problem. But must the exact nearest neighbor search problem suffer this curse? We provide some evidence in support of the curse. Specifically we investigate the exact nearest neighbor (static) search problem and the related problem of exact partial match within the asymmetric communication model first used by Miltersen to study data structure problems. We derive non-trivial asymptotic lower bounds for these exact problems that stand in contrast to known algorithms for approximate nearest neighbor search. Specifically, in the d-dimensional Hamming cube, we consider the nearest neighbour decision problem (i.e. in a preprocessed data base of n points does there exist a data base point that is within a specified distance L of the query point) and the partial match decision problem (i.e. given a query with both ``exposed'' and don't care coordinates, is there a vector in the preprocessed data base that exactly matches the query on the exposed coordinates). We assume that the dimension d is sufficiently large and growing with respect to the number of points. Using the richness technique of Miltersen, Nisan, Safra and Wigderson we show for randomized 2-sided error protocols solving the partial match problem (with log n + 1 exposed bits) that either the query player sends a total of Omega(log d log n) bits or the data base player sends a total of n^(1-e) bits where e is an arbitrarily small constant. Stronger lower bounds can be derived for the exact nearest neighbour problem. These communication lower bounds can be used to derive (weak but still interesting) lower bounds for the cell probe model (which seems to be the most general model for such problems).

 Joint work with Rafi Ostrovsky and Yuval Rabani