I. Abraham, Y. Bartal, T. H. Chan, K. Dhamdhere, A. Gupta et al., Metric embeddings with relaxed guarantees, Proc. of the 46th Annual IEEE Symp. on Foundations of Computer Science, FOCS '05, pp.83-100, 2005.

D. Achlioptas, Database-friendly random projections: Johnson-Lindenstrauss with binary coins, J. Comput. Syst. Sci, vol.66, issue.4, pp.671-687, 2003.

S. Arya, G. D. Da-fonseca, and D. M. Mount, Approximate polytope membership queries, Proc. 43rd Annual ACM Symp. Theory of Computing, STOC'11, pp.579-586, 2011.
URL : https://hal.archives-ouvertes.fr/hal-01890054

E. Anagnostopoulos, I. Z. Emiris, and I. Psarros, Low-quality dimension reduction and high-dimensional approximate nearest neighbor, Proc. 31st International Symp. on Computational Geometry (SoCG), pp.436-450, 2015.

A. Andoni and P. Indyk, E 2 LSH 0.1 User Manual, Implementation of LSH: E2LSH, 2005.

A. Andoni and P. Indyk, Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions, Commun. ACM, vol.51, issue.1, pp.117-122, 2008.

S. Arya, T. Malamatos, and D. M. Mount, Space-time tradeoffs for approximate nearest neighbor searching, J. ACM, vol.57, issue.1, 2009.

]. S. Amn-+-98, D. M. Arya, N. S. Mount, R. Netanyahu, A. Y. Silverman et al., An optimal algorithm for approximate nearest neighbor searching fixed dimensions, J. ACM, vol.45, issue.6, pp.891-923, 1998.

A. Andoni and I. Razenshteyn, Optimal data-dependent hashing for approximate near neighbors, the Proc. 47th ACM Symp. Theory of Computing, STOC'15, 2015.

Y. Bartal and L. Gottlieb, Approximate nearest neighbor search for $\ell p$-spaces ($2 < p < \infty$) via embeddings, 2015.

A. Beygelzimer, S. Kakade, and J. Langford, Cover trees for nearest neighbor, Proc. 23rd Intern. Conf. Machine Learning, ICML'06, pp.97-104, 2006.

Y. Bartal, B. Recht, and L. J. Schulman, Dimensionality reduction: Beyond the johnsonlindenstrauss bound, Proc. of the 22nd Annual ACM-SIAM Symp. on Discrete Algorithms, SODA '11, pp.868-887, 2011.

S. Dasgupta and Y. Freund, Random projection trees and low dimensional manifolds, Proc. 40th Annual ACM Symp. Theory of Computing, STOC'08, pp.537-546, 2008.

S. Dasgupta and A. Gupta, An elementary proof of a theorem of Johnson and Lindenstrauss, Random Struct. Algorithms, vol.22, issue.1, pp.60-65, 2003.

M. Datar, N. Immorlica, P. Indyk, and V. S. Mirrokni, Locality-sensitive hashing scheme based on p-stable distributions, Proc. 20th Annual Symp. Computational Geometry, SCG'04, pp.253-262, 2004.

L. Gottlieb and R. Krauthgamer, A nonlinear approach to dimension reduction, vol.54, pp.291-315, 2015.

A. Gupta, R. Krauthgamer, and J. R. Lee, Bounded geometries, fractals, and lowdistortion embeddings, Proc. 44th Annual IEEE Symp. Foundations of Computer Science, FOCS'03, pp.534-541, 2003.

, S. Har-Peled. Clustering motion. DCG, vol.31, issue.4, pp.545-565, 2004.

S. Har-peled, P. Indyk, and R. Motwani, Approximate nearest neighbor: Towards removing the curse of dimensionality, Theory of Computing, vol.8, issue.1, pp.321-350, 2012.

S. Har-peled and M. Mendel, Fast construction of nets in low dimensional metrics, and their applications, Proc. 21st Annual Symp. Computational Geometry, SCG'05, pp.150-158, 2005.

P. Indyk and R. Motwani, Approximate nearest neighbors: Towards removing the curse of dimensionality, Proc. 30th Annual ACM Symp. Theory of Computing, STOC'98, pp.604-613, 1998.

P. Indyk and A. Naor, Nearest-neighbor-preserving embeddings, ACM Trans. Algorithms, vol.3, issue.3, 2007.

H. Jegou, M. Douze, and C. Schmid, Product quantization for nearest neighbor search, IEEE Trans. on Pattern Analysis and Machine Intelligence, vol.33, issue.1, pp.117-128, 2011.
URL : https://hal.archives-ouvertes.fr/inria-00514462

W. Johnson and J. Lindenstrauss, Extensions of Lipschitz mappings into a Hilbert space, vol.26, pp.189-206, 1984.

R. Krauthgamer and J. R. Lee, Navigating nets: Simple algorithms for proximity search, Proc. 15th Annual ACM-SIAM Symp. Discrete Algorithms, SODA'04, pp.798-807, 2004.

D. R. Karger and M. Ruhl, Finding nearest neighbors in growth-restricted metrics, Proc. 34th Annual ACM Symp. Theory of Computing, STOC'02, pp.741-750, 2002.

S. Meiser, Point location in arrangements of hyperplanes, Inf. Comput, vol.106, issue.2, pp.286-303, 1993.

D. M. Mount, , 2010.

R. O&apos;donnell, Y. Wu, and Y. Zhou, Optimal lower bounds for locality-sensitive hashing (except when q is tiny), ACM Trans. Comput. Theory, vol.6, issue.1, 2014.

R. Panigrahy, Entropy based nearest neighbor search in high dimensions, Proc. 17th Annual ACM-SIAM Symp. Discrete Algorithms, SODA'06, pp.1186-1195, 2006.

S. Vempala, Randomly-oriented k-d trees adapt to intrinsic dimension, Proc. Foundations of Software Technology & Theor. Computer Science, pp.48-57, 2012.