Fast algorithms for nearest neighbor (NN) search have in large part focused on ℓ_2 distance. Here we develop an approach for ℓ_1 distance that begins with an explicit and exactly distance-preserving embedding of the points into ℓ_2~2. We show how this can efficiently be combined with random-projection based methods for ℓ_2 NN search, such as locality-sensitive hashing (LSH) or random projection trees. We rigorously establish the correctness of the methodology and show by experimentation using LSH that it is competitive in practice with available alternatives.
展开▼
