Database-friendly random projections: Johnson-Lindenstrauss with binary coins |
| |
Authors: | Dimitris Achlioptas |
| |
Affiliation: | Microsoft Research, One Microsoft Way, Redmond, WA 98052, USA |
| |
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 spherically random k-dimensional hyperplane through the origin. We give two constructions of such embeddings with the property that all elements of the projection matrix belong in {−1,0,+1}. Such constructions are particularly well suited for database environments, as the computation of the embedding reduces to evaluating a single aggregate over k random partitions of the attributes. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|