Dimensionality reduction techniques for proximity problems

In this paper we giveapproximation algorithms for several proximity problems in high dimensional spaces. In particular, we give the rst Las Vegas data structure for (1 +)-nearest neighbor with polynomial space and query time polynomial in dimension d and log n, wheren is the database size. We also give a deterministic 3-approximation algorithm with similar bounds� this is the rst deterministic constant factor approximation algorithm (with polynomial space) for any norm. For the closest pair problem we give a roughly n 1+ time Las Vegas algorithm with approximation factor O(1 = log 1 =) � this is the rst Las Vegas algorithm for this problem. Finally, we show a general reduction from the furthest point problem to the nearest neighbor problem. As a corollary, we improve the running time for the (1 +)-approximate diameter problem from n 2;O ( 2) to n 2;O ( ). Our results are uni ed by the fact that their key component is a dimensionality reduction technique for Hamming spaces.