Dimensionality reduction techniques for proximity problems
Piotr Indyk · 2000
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. 1