Poster
An algorithm for L1 nearest neighbor search via monotonic embedding
Xinan Wang · Sanjoy Dasgupta
Area 5+6+7+8 #104
Keywords: [ (Other) Classification ] [ (Other) Probabilistic Models and Methods ] [ Similarity and Distance Learning ] [ (Other) Machine Learning Topics ]
Fast algorithms for nearest neighbor (NN) search have in large part focused on L2 distance. Here we develop an approach for L1 distance that begins with an explicit and exact embedding of the points into L2. We show how this embedding can efficiently be combined with random projection methods for L2 NN search, such as locality-sensitive hashing or random projection trees. We rigorously establish the correctness of the methodology and show by experimentation that it is competitive in practice with available alternatives.
Live content is unavailable. Log in and register to view live content