Metric embeddings with relaxed guarantees, Proc. of the 46th Annual IEEE Symp. on Foundations of Computer Science, FOCS '05, pp.83-100, 2005. ,
Database-friendly random projections: Johnson-Lindenstrauss with binary coins, J. Comput. Syst. Sci, vol.66, issue.4, pp.671-687, 2003. ,
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
Low-quality dimension reduction and high-dimensional approximate nearest neighbor, Proc. 31st International Symp. on Computational Geometry (SoCG), pp.436-450, 2015. ,
E 2 LSH 0.1 User Manual, Implementation of LSH: E2LSH, 2005. ,
Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions, Commun. ACM, vol.51, issue.1, pp.117-122, 2008. ,
Space-time tradeoffs for approximate nearest neighbor searching, J. ACM, vol.57, issue.1, 2009. ,
An optimal algorithm for approximate nearest neighbor searching fixed dimensions, J. ACM, vol.45, issue.6, pp.891-923, 1998. ,
Optimal data-dependent hashing for approximate near neighbors, the Proc. 47th ACM Symp. Theory of Computing, STOC'15, 2015. ,
Approximate nearest neighbor search for $\ell p$-spaces ($2 < p < \infty$) via embeddings, 2015. ,
Cover trees for nearest neighbor, Proc. 23rd Intern. Conf. Machine Learning, ICML'06, pp.97-104, 2006. ,
Dimensionality reduction: Beyond the johnsonlindenstrauss bound, Proc. of the 22nd Annual ACM-SIAM Symp. on Discrete Algorithms, SODA '11, pp.868-887, 2011. ,
Random projection trees and low dimensional manifolds, Proc. 40th Annual ACM Symp. Theory of Computing, STOC'08, pp.537-546, 2008. ,
An elementary proof of a theorem of Johnson and Lindenstrauss, Random Struct. Algorithms, vol.22, issue.1, pp.60-65, 2003. ,
Locality-sensitive hashing scheme based on p-stable distributions, Proc. 20th Annual Symp. Computational Geometry, SCG'04, pp.253-262, 2004. ,
A nonlinear approach to dimension reduction, vol.54, pp.291-315, 2015. ,
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.
Approximate nearest neighbor: Towards removing the curse of dimensionality, Theory of Computing, vol.8, issue.1, pp.321-350, 2012. ,
Fast construction of nets in low dimensional metrics, and their applications, Proc. 21st Annual Symp. Computational Geometry, SCG'05, pp.150-158, 2005. ,
Approximate nearest neighbors: Towards removing the curse of dimensionality, Proc. 30th Annual ACM Symp. Theory of Computing, STOC'98, pp.604-613, 1998. ,
Nearest-neighbor-preserving embeddings, ACM Trans. Algorithms, vol.3, issue.3, 2007. ,
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
Extensions of Lipschitz mappings into a Hilbert space, vol.26, pp.189-206, 1984. ,
Navigating nets: Simple algorithms for proximity search, Proc. 15th Annual ACM-SIAM Symp. Discrete Algorithms, SODA'04, pp.798-807, 2004. ,
Finding nearest neighbors in growth-restricted metrics, Proc. 34th Annual ACM Symp. Theory of Computing, STOC'02, pp.741-750, 2002. ,
Point location in arrangements of hyperplanes, Inf. Comput, vol.106, issue.2, pp.286-303, 1993. ,
, , 2010.
Optimal lower bounds for locality-sensitive hashing (except when q is tiny), ACM Trans. Comput. Theory, vol.6, issue.1, 2014. ,
Entropy based nearest neighbor search in high dimensions, Proc. 17th Annual ACM-SIAM Symp. Discrete Algorithms, SODA'06, pp.1186-1195, 2006. ,
Randomly-oriented k-d trees adapt to intrinsic dimension, Proc. Foundations of Software Technology & Theor. Computer Science, pp.48-57, 2012. ,