  We show an analog to the Fast Johnson-Lindenstrauss Transform for Nearest
Neighbor Preserving Embeddings in $\ell_2$. These are sparse, randomized
embeddings that preserve the (approximate) nearest neighbors. The
dimensionality of the embedding space is bounded not by the size of the
embedded set n, but by its doubling dimension {\lambda}. For most large
real-world datasets this will mean a considerably lower-dimensional embedding
space than possible when preserving all distances. The resulting embeddings can
be used with existing approximate nearest neighbor data structures to yield
speed improvements.
