Timezone: »
Poster
An algorithm for L1 nearest neighbor search via monotonic embedding
Xinan Wang · Sanjoy Dasgupta
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.
Author Information
Xinan Wang (UCSD)
Sanjoy Dasgupta (UC San Diego)
More from the Same Authors
-
2018 Poster: Interactive Structure Learning with Structural Query-by-Committee »
Christopher Tosh · Sanjoy Dasgupta -
2018 Spotlight: Interactive Structure Learning with Structural Query-by-Committee »
Christopher Tosh · Sanjoy Dasgupta -
2014 Poster: Rates of Convergence for Nearest Neighbor Classification »
Kamalika Chaudhuri · Sanjoy Dasgupta -
2014 Spotlight: Rates of Convergence for Nearest Neighbor Classification »
Kamalika Chaudhuri · Sanjoy Dasgupta -
2013 Poster: The Fast Convergence of Incremental PCA »
Akshay Balsubramani · Sanjoy Dasgupta · Yoav Freund -
2010 Poster: Rates of convergence for the cluster tree »
Kamalika Chaudhuri · Sanjoy Dasgupta -
2007 Spotlight: A general agnostic active learning algorithm »
Sanjoy Dasgupta · Daniel Hsu · Claire Monteleoni -
2007 Session: Session 3: Theory and Sequential Decision Making »
Sanjoy Dasgupta -
2007 Poster: A general agnostic active learning algorithm »
Sanjoy Dasgupta · Daniel Hsu · Claire Monteleoni -
2007 Poster: Learning the structure of manifolds using random projections »
Yoav S Freund · Sanjoy Dasgupta · Mayank Kabra · Nakul Verma -
2007 Poster: A learning framework for nearest neighbor search »
Lawrence Cayton · Sanjoy Dasgupta