research-article

Random projection trees and low dimensional manifolds

Authors:

Sanjoy Dasgupta,

Yoav FreundAuthors Info & Claims

STOC '08: Proceedings of the fortieth annual ACM symposium on Theory of computing

Pages 537 - 546

https://doi.org/10.1145/1374376.1374452

Published: 17 May 2008 Publication History

Abstract

We present a simple variant of the k-d tree which automatically adapts to intrinsic low dimensional structure in data without having to explicitly learn this structure.

References

[1]

S. Arya, D. Mount, N. Netanyahu, R. Silverman, and A. Wu. An optimal algorithm for approximate nearest neighbor searching. Journal of the ACM, 45:891--923, 1998.

Digital Library

[2]

P. Assouad. Plongements lipschitziens dans rn. Bull. Soc. Math. France, 111(4):429--448, 1983.

[3]

M. Belkin and P. Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. Neural Computation, 15(6):1373--1396, 2003.

Digital Library

[4]

J. Bentley. Multidimensional binary search trees used for associative searching. Communications of the ACM, 18(9):509--517, 1975.

Digital Library

[5]

A. Beygelzimer, S. Kakade, and J. Langford. Cover trees for nearest neighbor. In 23rd International Conference on Machine Learning, 2006.

Digital Library

[6]

E. Candes and T. Tao. Near optimal signal recovery from random projections: universal encoding strategies? IEEE Transactions on Information Theory, 52(12):5406--5425, 2006.

Digital Library

[7]

P. Chou, T. Lookabaugh, and R. Gray. Optimal pruning with applications to tree--structured source coding and modeling. IEEE Transactions on Information Theory, 35(2):299--315, 1989.

Digital Library

[8]

L. Devroye, L. Gyorfi, and G. Lugosi. A Probabilistic Theory of Pattern Recognition. Springer, 1996.

[9]

M. do Carmo. Riemannian Geometry. Birkhauser, 1992.

[10]

D. Donoho. Compressed sensing. IEEE Transactions on Information Theory, 52(4):1289--1306, 2006.

Digital Library

[11]

R. Durrett. Probability: Theory and Examples. Duxbury, second edition, 1995.

[12]

Y. Freund, S. Dasgupta, M. Kabra, and N. Verma. Learning the structure of manifolds using random projections. In Neural Information Processing Systems, 2007.

[13]

H. Fuchs, Z. Kedem, and B. Naylor. On visible surface generation by a priori tree structures. Computer Graphics, 14(3):124--133, 1980.

Digital Library

[14]

A. Gionis, P. Indyk, and R. Motwani. Similarity search in high dimensions via hashing. In 25th International Conference on Very Large Databases, 1999.

Digital Library

[15]

S. Graf and H. Luschgy. Foundations of quantization for probability distributions. Springer, 2000.

[16]

R. Gray and D. Neuhoff. Quantization. IEEE Transactions on Information Theory, 44(6):2325--2383, 1998.

Digital Library

[17]

A. Gupta, R. Krauthgamer, and J. Lee. Bounded geometries, fractals, and low--distortion embeddings. In IEEE Symposium on Foundations of Computer Science, pages 534--544, 2003.

Digital Library

[18]

J. Heinonen. Lectures on Analysis on Metric Spaces. Springer, 2001.

[19]

P. Indyk and A. Naor. Nearest neighbor preserving embeddings. ACM Transactions on Algorithms, 3(3), 2007.

Digital Library

[20]

R. Krauthgamer and J. Lee. Navigating nets: simple algorithms for proximity search. In ACM--SIAM Symposium on Discrete Algorithms, 2004.

Digital Library

[21]

T. Liu, A. Moore, A. Gray, and K. Yang. An investigation of practical approximate nearest neighbor algorithms. In Neural Information Processing Systems, 2004.

[22]

P. Niyogi, S. Smale, and S. Weinberger. Finding the homology of submanifolds with high confidence from random samples. Discrete and Computational Geometry, 2006.

Digital Library

[23]

S. Roweis and L. Saul. Nonlinear dimensionality reduction by locally linear embedding. Science, (290):2323--2326, 2000.

[24]

J. Tenenbaum, V. de Silva, and J. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, 290(5500):2319--2323, 2000.

Cited By

Wei JLee XLiao ZPalpanas TPeng B(2025)Subspace Collision: An Efficient and Accurate Framework for High-dimensional Approximate Nearest Neighbor SearchProceedings of the ACM on Management of Data10.1145/37097293:1(1-29)Online publication date: 11-Feb-2025
https://dl.acm.org/doi/10.1145/3709729
Kang JMin J(2024)Fault Detection Method in the Startup Operation of Nuclear Power PlantsJournal of Power System Engineering10.9726/kspse.2024.28.2.02728:2(27-33)Online publication date: 30-Apr-2024
https://doi.org/10.9726/kspse.2024.28.2.027
Tiwari MKang RLee JLee DPiech CThrun SShomorony IZhang MSalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)Faster maximum inner product search in high dimensionsProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3694045(48344-48361)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3694045
Show More Cited By

Recommendations

Random projection in dimensionality reduction: applications to image and text data
KDD '01: Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining

Random projections have recently emerged as a powerful method for dimensionality reduction. Theoretical results indicate that the method preserves distances quite nicely; however, empirical results are sparse. We present experimental results on using ...
Efficient clustering on Riemannian manifolds

Reformulating computer vision problems over Riemannian manifolds has demonstrated superior performance in various computer vision applications. This is because visual data often forms a special structure lying on a lower dimensional space embedded in a ...
Informed Weighted Random Projection for Dimension Reduction
ADMA 2013: Part II of the Proceedings of the 9th International Conference on Advanced Data Mining and Applications - Volume 8347

Dimensionality reduction is a frequent pre-processing step in classification tasks. It helps to improve the accuracy of classification by better representing the dataset and also alleviates the curse of dimensionality by reducing the number of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '08: Proceedings of the fortieth annual ACM symposium on Theory of computing

May 2008

712 pages

ISBN:9781605580470

DOI:10.1145/1374376

General Chair:
Richard Ladner
University of Washington
,
Program Chair:
Cynthia Dwork
Microsoft Research, Silicon Valley

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 May 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

STOC '08

Sponsor:

STOC '08: Symposium on Theory of Computing

May 17 - 20, 2008

British Columbia, Victoria, Canada

Acceptance Rates

STOC '08 Paper Acceptance Rate 80 of 325 submissions, 25%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

216
Total Citations
View Citations
1,374
Total Downloads

Downloads (Last 12 months)121
Downloads (Last 6 weeks)14

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Wei JLee XLiao ZPalpanas TPeng B(2025)Subspace Collision: An Efficient and Accurate Framework for High-dimensional Approximate Nearest Neighbor SearchProceedings of the ACM on Management of Data10.1145/37097293:1(1-29)Online publication date: 11-Feb-2025
https://dl.acm.org/doi/10.1145/3709729
Kang JMin J(2024)Fault Detection Method in the Startup Operation of Nuclear Power PlantsJournal of Power System Engineering10.9726/kspse.2024.28.2.02728:2(27-33)Online publication date: 30-Apr-2024
https://doi.org/10.9726/kspse.2024.28.2.027
Tiwari MKang RLee JLee DPiech CThrun SShomorony IZhang MSalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)Faster maximum inner product search in high dimensionsProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3694045(48344-48361)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3694045
Subedi SSumida TPark Y(2024)A scalable approach to topic modelling in single-cell data by approximate pseudobulk projectionLife Science Alliance10.26508/lsa.2024027137:10(e202402713)Online publication date: 6-Aug-2024
https://doi.org/10.26508/lsa.202402713
Ross LHorn JPilanci MLuo KZhou G(2024)Bottom Up vs Top Down: What Does Firm 10-K Tell Us?SSRN Electronic Journal10.2139/ssrn.4747519Online publication date: 2024
https://doi.org/10.2139/ssrn.4747519
Wang ZWang QCheng XWang PPalpanas TWang W(2024)Steiner-Hardness: A Query Hardness Measure for Graph-Based ANN IndexesProceedings of the VLDB Endowment10.14778/3704965.370497417:13(4668-4682)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.14778/3704965.3704974
Wei JPeng BLee XPalpanas T(2024)DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor SearchProceedings of the VLDB Endowment10.14778/3665844.366585417:9(2241-2254)Online publication date: 1-May-2024
https://dl.acm.org/doi/10.14778/3665844.3665854
Elliott OClark JOosterhuis HBast HXiong C(2024)The Impacts of Data, Ordering, and Intrinsic Dimensionality on Recall in Hierarchical Navigable Small WorldsProceedings of the 2024 ACM SIGIR International Conference on Theory of Information Retrieval10.1145/3664190.3672512(25-33)Online publication date: 2-Aug-2024
https://dl.acm.org/doi/10.1145/3664190.3672512
Gao JLong C(2024)RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor SearchProceedings of the ACM on Management of Data10.1145/36549702:3(1-27)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1145/3654970
Patel LKraft PGuestrin CZaharia M(2024)ACORN: Performant and Predicate-Agnostic Search Over Vector Embeddings and Structured DataProceedings of the ACM on Management of Data10.1145/36549232:3(1-27)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1145/3654923
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten