Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform

Full text

Pdf (231 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirty-eighth annual ACM symposium on Theory of computing table of contents

Seattle, WA, USA

SESSION: Session 13B table of contents

Pages: 557 - 563

Year of Publication: 2006

ISBN:1-59593-134-1

Authors

Nir Ailon	Princeton University, Princeton, NJ
Bernard Chazelle	Princeton University, Princeton, NJ

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 24, Downloads (12 Months): 108, Citation Count: 13

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1132516.1132597 What is a DOI?

ABSTRACT

We introduce a new low-distortion embedding of l₂^d into l_p^{O(log n)} (p=1,2), called the Fast-Johnson-Linden-strauss-Transform. The FJLT is faster than standard random projections and just as easy to implement. It is based upon the preconditioning of a sparse projection matrix with a randomized Fourier transform. Sparse random projections are unsuitable for low-distortion embeddings. We overcome this handicap by exploiting the "Heisenberg principle" of the Fourier transform, ie, its local-global duality. The FJLT can be used to speed up search algorithms based on low-distortion embeddings in l₁ and l₂. We consider the case of approximate nearest neighbors in l₂^d. We provide a faster algorithm using classical projections, which we then further speed up by plugging in the FJLT. We also give a faster algorithm for searching over the hypercube.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Dimitris Achlioptas, Database-friendly random projections: Johnson-Lindenstrauss with binary coins, Journal of Computer and System Sciences, v.66 n.4, p.671-687, 1 June 2003 [doi>10.1016/S0022-0000(03)00025-4]
	2	Alon, N., Spencer, J. The probabilistic method, John Wiley, 2nd edition, 2000.
	3	Alon, N. Problems and results in extremal combinatorics, I, Discrete Math. 273 (2003), 31--53.
	4	Sunil Arya , David M. Mount, Approximate nearest neighbor queries in fixed dimensions, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.271-280, January 25-27, 1993, Austin, Texas, United States
	5	Sunil Arya , David M. Mount , Nathan S. Netanyahu , Ruth Silverman , Angela Y. Wu, An optimal algorithm for approximate nearest neighbor searching fixed dimensions, Journal of the ACM (JACM), v.45 n.6, p.891-923, Nov. 1998 [doi>10.1145/293347.293348]
	6	Marshall Bern, Approximate closest-point queries in high dimensions, Information Processing Letters, v.45 n.2, p.95-99, Feb. 26, 1993 [doi>10.1016/0020-0190(93)90222-U]
	7	Ella Bingham , Heikki Mannila, Random projection in dimensionality reduction: applications to image and text data, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.245-250, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502546]
	8	Allan Borodin , Rafail Ostrovsky , Yuval Rabani, Lower bounds for high dimensional nearest neighbor search and related problems, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.312-321, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301330]
	9	Carlen, E. A., Carvalho, M. C., Loss, M. Determination of the Spectral Gap for Kac's Master Equation and Related Stochastic Evolutions, Preprint arXiv:math-ph/0109003, (2000)
	10	Amit Chakrabarti , Oded Regev, An Optimal Randomised Cell Probe Lower Bound for Approximate Nearest Neighbour Searching, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.473-482, October 17-19, 2004 [doi>10.1109/FOCS.2004.12]
	11	Timothy M. Chan, Approximate nearest neighbor queries revisited, Proceedings of the thirteenth annual symposium on Computational geometry, p.352-358, June 04-06, 1997, Nice, France [doi>10.1145/262839.263001]
	12	Kenneth L. Clarkson, An algorithm for approximate closest-point queries, Proceedings of the tenth annual symposium on Computational geometry, p.160-164, June 06-08, 1994, Stony Brook, New York, United States [doi>10.1145/177424.177609]
	13	Kenneth L. Clarkson, Nearest neighbor queries in metric spaces, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.609-617, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258655]
	14	Dasgupta, S., Gupta, A. An elementary proof of the Johnson-Lindenstrauss lemma, Technical Report 99-006, UC Berkeley, March 1999.
	15	Diaconis, P., Saloff-Coste, L. Bounds for Kac's Master Equation, Communications in Mathematical Physics 209(3), (2000), 729--755
	16	Martin Farach-Colton , Piotr Indyk, Approximate Nearest Neighbor Algorithms for Hausdorff Metrics via Embeddings, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.171, October 17-18, 1999
	17	U. Feige , D. Peleg , P. Raghavan , E. Upfal, Computing with unreliable information, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.128-137, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100230]
	18	P. Frankl , H. Maehara, The Johnson-Lindenstrauss Lemma and the sphericity of some graphs, Journal of Combinatorial Theory Series A, v.44 n.3, p.355-362, June 1987
	19	S. Har-Peled, A Replacement for Voronoi Diagrams of Near Linear Size, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.94, October 14-17, 2001
	20	Hastings, W. Monte Carlo sampling methods using Markov chains and their applications, Biometrica 57, 97--109
	21	P. Indyk, On Approximate Nearest Neighbors in Non-Euclidean Spaces, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.148, November 08-11, 1998
	22	Piotr Indyk , Rajeev Motwani, High-dimensional computational geometry, 2001
	23	Piotr Indyk, Dimensionality reduction techniques for proximity problems, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.371-378, January 09-11, 2000, San Francisco, California, United States
	24	Indyk, P. Nearest neighbors in high-dimensional spaces, Handbook of Discrete and Computational Geometry, eds., J.E. Goodman and J. O'Rourke, CRC Press (2004).
	25	Indyk, P., Matousek, J. Low-distortion embeddings of finite metric spaces, Handbook of Discrete and Computational Geometry, eds., J.E. Goodman and J. O'Rourke, CRC Press (2004).
	26	Piotr Indyk , Rajeev Motwani, Approximate nearest neighbors: towards removing the curse of dimensionality, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.604-613, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276876]
	27	Johnson, W.B., Lindenstrauss, J. Extensions of Lipschitz mappings into a Hilbert space, Contemp. Math. 26 (1984), 189--206.
	28	Kac, M. Probability and related topics in physical science, Wiley Interscience, N.Y.
	29	Jon M. Kleinberg, Two algorithms for nearest-neighbor search in high dimensions, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.599-608, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258653]
	30	Eyal Kushilevitz , Rafail Ostrovsky , Yuval Rabani, Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces, SIAM Journal on Computing, v.30 n.2, p.457-474, 2000 [doi>10.1137/S0097539798347177]
	31	Jiri Matousek, Lectures on Discrete Geometry, Springer-Verlag New York, Inc., Secaucus, NJ, 2002
	32	S. Muthukrishnan , Süleyman Cenk Sahinalp, Simple and Practical Sequence Nearest Neighbors with Block Operations, Proceedings of the 13th Annual Symposium on Combinatorial Pattern Matching, p.262-278, July 03-05, 2002
	33	Igor Pak, Using stopping times to bound mixing times, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.953-954, January 17-19, 1999, Baltimore, Maryland, United States
	34	Peter N. Yianilos, Data structures and algorithms for nearest neighbor search in general metric spaces, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.311-321, January 25-27, 1993, Austin, Texas, United States
	35	Peter N. Yianilos, Locally lifting the curse of dimensionality for nearest neighbor search (extended abstract), Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.361-370, January 09-11, 2000, San Francisco, California, United States

CITED BY 13

	Wei Wang , Minos Garofalakis , Kannan Ramchandran, Distributed sparse random projections for refinable approximation, Proceedings of the 6th international conference on Information processing in sensor networks, April 25-27, 2007, Cambridge, Massachusetts, USA
	Piotr Indyk, Uncertainty principles, extractors, and explicit embeddings of l2 into l1, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
	Nir Ailon , Edo Liberty, Fast dimension reduction using Rademacher series on dual BCH codes, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.1-9, January 20-22, 2008, San Francisco, California
	T-H. Hubert Chan , Anupam Gupta , Kunal Talwar, Ultra-low-dimensional embeddings for doubling metrics, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.333-342, January 20-22, 2008, San Francisco, California
	William B. Johnson , Assaf Naor, The Johnson-Lindenstrauss lemma almost characterizes Hilbert space, but not quite, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.885-891, January 04-06, 2009, New York, New York
	Kenneth L. Clarkson, Tighter bounds for random projections of manifolds, Proceedings of the twenty-fourth annual symposium on Computational geometry, June 09-11, 2008, College Park, MD, USA
	Alexandr Andoni , Piotr Indyk, Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions, Communications of the ACM, v.51 n.1, January 2008
	Anirban Dasgupta , Petros Drineas , Boulos Harb , Ravi Kumar , Michael W. Mahoney, Sampling algorithms and coresets for ℓ_p regression, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.932-941, January 20-22, 2008, San Francisco, California
	Ping Li, Very sparse stable random projections for dimension reduction in lα (0 <α ≤ 2) norm, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA
	Ping Li, Estimators and tail bounds for dimension reduction in lα (0 < α ≤ 2) using stable random projections, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.10-19, January 20-22, 2008, San Francisco, California
	Yu-En Lu , Pietro Lió , Steven Hand, On low dimensional random projections and similarity search, Proceeding of the 17th ACM conference on Information and knowledge management, October 26-30, 2008, Napa Valley, California, USA
	Nam H. Nguyen , Thong T. Do , Trac D. Tran, A fast and efficient algorithm for low-rank approximation of a matrix, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA
	Edo Liberty , Steven W. Zucker, The Mailman algorithm: A note on matrix--vector multiplication, Information Processing Letters, v.109 n.3, p.179-182, January, 2009