Andoni and Indyk presented a paper in FOCS 2006: Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. In this paper they present an algorithm for the $c$-approximate nearest neighbor problem in $d$-dimensional Euclidean space in with query time $O(dn^{1/c^2 + o(1)})$ and space $O(dn + n^{1+ 1/c^2 + o(1)})$. The results are based on Locality Sensitive Hashing, i.e. all the points are hashed and a given query point $q$ will have a high probability of collision with a point $p$ if $p$ and $q$ are close to each other.
Is it possible to first preprocess with some dimension reduction technique and then apply the same Andoni / Indyk algorithm?
For example, we could apply a Johnson-Lindenstrauss Transform. Apparently the JL flattening theorem states that "any $n$ points in Euclidean space can be embedded into $O(\epsilon^{−2} \log n)$ dimensions so that all pairwise Euclidean distances are preserved up to $1± \epsilon$."
Thus, could we first preprocess by embedding the points into $O(\epsilon^{−2} \log n)$ dimensions and thus improve the space and query time bounds given by Andoni and Indyk?
I can't find any concrete technical reasons why this shouldn't work, but it also seems like if this does work, then I should be able to find a reference documenting it.
More detail:
I see now that Andoni and Indyk are already performing a dimension reduction. From the paragraph above section 3.2: "To reduce U, we project $ℜ^d$ to a lower-dimensional space $ℜ^t$ via a random dimensionality reduction. The parameter $t$ is $o(log n)$."
At first this made me think that another dimension reduction would be redundant.
However, there is still a factor of $d$ in the query time! This is because the LSH based query algorithm requires $O(n^\rho)$ hashing function evaluations, and each hash function (when hashing a $d$-dimensional point) requires $O(d)$ operations (according to IM98).
Therefore, if we want to reduce the dependence on $d$ in the query time while using a LSH based approach, we need to speed up the evaluation of the hash function. One way to do this would be to preprocess all the points, projecting them into $O(\epsilon^{−2} \log n)$ dimensions. The Andoni/Indyk algorithm will make another projection into $R^t$, where $t = o(\log n)$. However, when running the query algorithm, we make 1 projection of the query point into $e = \epsilon^{−2} \log n$ dimensions first, and so each of the $O(n^\rho)$ hash function evaluations is only evaluated on $e$-dimensional points instead of $d$ dimensional points. This should speed up the query time to $O(e\cdot n^\rho) = O(\epsilon^{−2} \log n \cdot n^\rho) < O(dn^\rho) $ when $d$ is large.
