Database-friendly random projections

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Database-friendly random projections

Full text

Pdf (183 KB)

Source

Symposium on Principles of Database Systems archive
Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems table of contents

Santa Barbara, California, United States

Pages: 274 - 281

Year of Publication: 2001

ISBN:1-58113-361-8

Author

Dimitris Achlioptas

Microsoft Corporation, One Microsoft Way, Red-mond, WA

Sponsor

SIGMOD: ACM Special Interest Group on Management of Data

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 57, Citation Count: 29

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/375551.375608 What is a DOI?

ABSTRACT

A classic result of Johnson and Lindenstrauss asserts that any set of n points in d-dimensional Euclidean space can be embedded into k-dimensional Euclidean space where k is logarithmic in n and independent of d so that all pairwise distances are maintained within an arbitrarily small factor. All known constructions of such embeddings involve projecting the n points onto a random k-dimensional hyperplane. We give a novel construction of the embedding, suitable for database applications, which amounts to computing a simple aggregate over k random attribute partitions.

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	S. Arora and R. Kannan. Learning mixtures of arbitrary Gaussians. Submitted, 2000.
	2	Sanjoy Dasgupta, Learning Mixtures of Gaussians, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.634, October 17-18, 1999
	3	S. Dasgupta and A. Gupta. An elementary proof of the Johnson-Lindenstrauss lemma. Technical report 99-006, UC Berkeley, March 1999.
	4	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
	5	P. Indyk, Stable distributions, pseudorandom generators, embeddings and data stream computation, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.189, November 12-14, 2000
	6	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]
	7	W. B. Johnson and J. Lindenstrauss. Extensions of Lipschitz mappings into a Hilbert space. In Conference in modern analysis and probability (New Haven, Conn., 1982), pages 189-206. Amer. Math. Soc., Providence, R.I., 1984.
	8	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]
	9	N. Linial, E. London, and Y. Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15(2):215-245, 1995.
	10	Christos H. Papadimitriou , Hisao Tamaki , Prabhakar Raghavan , Santosh Vempala, Latent semantic indexing: a probabilistic analysis, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.159-168, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275505]
	11	Leonard J. Schulman, Clustering for edge-cost minimization (extended abstract), Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.547-555, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335373]
	12	Santosh Vempala, A Random Sampling based Algorithm for Learning the Intersection of Half-spaces, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.508, October 19-22, 1997
	13	Rosa I. Arriaga , Santosh Vempala, An Algorithmic Theory of Learning: Robust Concepts and Random Projection, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.616, October 17-18, 1999

CITED BY 29

	D. Sivakumar, Algorithmic derandomization via complexity theory, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Charu C. Aggarwal, Hierarchical subspace sampling: a unified framework for high dimensional data reduction, selectivity estimation and nearest neighbor search, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin
	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
	Tamraparni Dasu , Theodore Johnson , S. Muthukrishnan , Vladislav Shkapenyuk, Mining database structure; or, how to build a data quality browser, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin
	Moses Charikar , Kevin Chen , Martin Farach-Colton, Finding frequent items in data streams, Theoretical Computer Science, v.312 n.1, p.3-15, 26 January 2004
	Sanjoy Dasgupta , Anupam Gupta, An elementary proof of a theorem of Johnson and Lindenstrauss, Random Structures & Algorithms, v.22 n.1, p.60-65, January 2003
	Dmitriy Fradkin , David Madigan, Experiments with random projections for machine learning, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C.
	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
	Lars Engebretsen , Piotr Indyk , Ryan O'Donnell, Derandomized dimensionality reduction with applications, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.705-712, January 06-08, 2002, San Francisco, California
	Charu C. Aggarwal, An Efficient Subspace Sampling Framework for High-Dimensional Data Reduction, Selectivity Estimation, and Nearest-Neighbor Search, IEEE Transactions on Knowledge and Data Engineering, v.16 n.10, p.1247-1262, October 2004
	Sariel Har-Peled , Kasturi Varadarajan, Projective clustering in high dimensions using core-sets, Proceedings of the eighteenth annual symposium on Computational geometry, p.312-318, June 05-07, 2002, Barcelona, Spain
	Gísli R. Hjaltason , Hanan Samet, Properties of Embedding Methods for Similarity Searching in Metric Spaces, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.25 n.5, p.530-549, May 2003
	Lance Parsons , Ehtesham Haque , Huan Liu, Subspace clustering for high dimensional data: a review, ACM SIGKDD Explorations Newsletter, v.6 n.1, p.90-105, June 2004
	Richard Cole , Dennis Shasha , Xiaojian Zhao, Fast window correlations over uncooperative time series, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA
	Kaushal Sanghai , Ting Su , Jennifer Dy , David Kaeli, A multinomial clustering model for fast simulation of computer architecture designs, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA
	Bo Brinkman , Moses Charikar, On the impossibility of dimension reduction in l₁, Journal of the ACM (JACM), v.52 n.5, p.766-788, September 2005
	Rosa I. Arriaga , Santosh Vempala, An algorithmic theory of learning: Robust concepts and random projection, Machine Learning, v.63 n.2, p.161-182, May 2006
	M. Sahlgren , J. Karlgren, Automatic bilingual lexicon acquisition using random indexing of parallel corpora, Natural Language Engineering, v.11 n.3, p.327-341, September 2005
	Daniel A. Spielman , Nikhil Srivastava, Graph sparsification by effective resistances, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	José J. Amador, Random projection and orthonormality for lossy image compression, Image and Vision Computing, v.25 n.5, p.754-766, May, 2007
	Pankaj K. Agarwal , Sariel Har-Peled , Hai Yu, Embeddings of surfaces, curves, and moving points in euclidean space, Proceedings of the twenty-third annual symposium on Computational geometry, June 06-08, 2007, Gyeongju, South Korea
	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
	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
	Guoping Qiu , Jianzhong Fang, Classification in an informative sample subspace, Pattern Recognition, v.41 n.3, p.949-960, March, 2008
	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
	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
	Sharon Goldberg , David Xiao , Eran Tromer , Boaz Barak , Jennifer Rexford, Path-quality monitoring in the presence of adversaries, ACM SIGMETRICS Performance Evaluation Review, v.36 n.1, June 2008
	Kyu-Hwa Jeong , Jose C. Principe, Enhancing the correntropy MACE filter with random projections, Neurocomputing, v.72 n.1-3, p.102-111, December, 2008
	Roberto Avogadri , Giorgio Valentini, Fuzzy ensemble clustering based on random projections for DNA microarray data analysis, Arificial Intelligence in Medicine, v.45 n.2-3, p.173-183, February, 2009