An algorithm for 1 nearest neighbor search via monotonic embedding
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.
The paper shows an embedding from l_1 into l_2-squared, for the application of nearest neighbor search. The embedding method can be adapted for a new out-of-sample extension (i.e., a previously unseen query point). The authors also show experiments showing the competitiveness of their method.
While the fundamental technical contribution is interesting and should be published, the contextualization is very far from ideal. Here are some points that the authors should address: - besides the l_1 methods based on Cauchy distribution, there is also LSH methods directly for the l_1 space: just impose a randomly shifted grid (see, e.g., the description in the CACM article by Andoni & Indyk). - it is not clear than embedding l_1 into l_2^2 would be the best way to tackly the l_1 problem. In particular, if we want to solve a c-approximation under l_1, this would translate into requiring a \sqrt{c} approximation for l_2 after the embedding. I.e., the resulting problem in l_2 is harder! Luckily, in l_2, LSH achieves runtime n^{1/c^2} (cf, l_1 achieves runtime n^{1/c}); however the corresponding l_2 algorithns are much harder (compare the algorithms from  the reference [10] versus [5]). Thus, it seems more beneficial to tackle l_1 problem directly. It is possible that, in practice, l_2 algorithms are much more performant, but this need to be argued well.  The authors should mention also that an embedding from l_1 into l_2-squared is actually known from [Linial, London, Rabunovich, Combinatorica 1995]. That embedding proceeds by embedding l_1 into Hamming space using unary embedding, and then embedding Hamming into l_2-squared using identity mapping. Its disadvantage is that the "scale" needs to be known to achieve a bounded dimension (which is a common assumption in LSH in fact).  The algorithm from this paper in fact can be seen as an efficient application of the JL dimension reduction on the embedding resulting from the LLR construction. This is what I find the most interesting contribution in this paper, and it should be played up. However, I cannot recommend a positive score due to the issues from above.