Database-friendly random projections
Top Cited Papers
- 1 May 2001
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 274-281
- https://doi.org/10.1145/375551.375608
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.Keywords
This publication has 5 references indexed in Scilit:
- Clustering for edge-cost minimization (extended abstract)Published by Association for Computing Machinery (ACM) ,2000
- Latent semantic indexingPublished by Association for Computing Machinery (ACM) ,1998
- Approximate nearest neighborsPublished by Association for Computing Machinery (ACM) ,1998
- Two algorithms for nearest-neighbor search in high dimensionsPublished by Association for Computing Machinery (ACM) ,1997
- The geometry of graphs and some of its algorithmic applicationsCombinatorica, 1995