Better algorithms for high-dimensional proximity problems via asymmetric embeddings
Piotr Indyk · 2003
Abstract In this paper we give several results based on randomized embeddings of l2 into l1 (or "l1-like") spaces. Our first result is a (1 + ffl)-distortion asymmetric embedding of n points in l2 into l1 with polylog(n) dimension, for any 1 + ffl. This gives the first known O(1)- approximate nearest neighbor algorithm with fast query time and almost polynomial space for a product of Euclidean norms, a common generalization of both l2 and l1 norms. Our embedding also clarifies the relative complexity of approximate nearest neighbor in l2 and l1 spaces. Our second result in a (1+ffl)-approximate algorithm for the diameter of n points in ld2, running in time ~O(dn1+1=(1+ffl)2); the algorithm is fully dynamic. This improves several previous algorithms for this problem (see Table 1 for more information). 1 Introduction Embeddings between normed spaces are known to be very useful tools for designing geometric algorithms. A classic example is an O(2dn)-time algorithm for computing diameter of n points in ld1 [GBT84]: since the problem seems difficult in the original space, we can embed1 ld1 isometrically into l2