6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ my answer: yes it will work depending on the distribution of your datapoints. the more random they are distributed, the less it will work. the dimension reduction is basically a compression step that succeeds if the points tend to be "nearby" each other. so it seems it would depend on the application. another standard dimensional reduction strategy is SVD, singular value decomposition. presumably/typically datapoints would already be compressed this way before being entered into the database with the query algorithm. $\endgroup$ – vzn Feb 3 '12 at 1:17
  • $\begingroup$ It doesn't seem that either LSH or JLT depend on the distribution of the data points for the worst case theoretical results, so why should the combination? $\endgroup$ – Joe Feb 3 '12 at 4:59
  • $\begingroup$ have you heard of anyone actually applying these algorithms to real data? the papers are purely theoretical. eg in the JLT paper see the appendix where they talk about tightness, distortion, and sparsity. sparsity is probably basically an assumption or measure of how "near" points are in a distribution ie an assumption about randomness vs order of the pts... as for the LSH paper, hashing algorithms will tend to deteriorate in performance for some "uneven" (worst case) distributions of data. etc. $\endgroup$ – vzn Feb 3 '12 at 5:28
  • 3
    $\begingroup$ The idea of dimension reduction was used in the original papers on ANN in high dimensions (see [IM98]). They did not write it that way in the later paper, because I think they implicitly assumed that $d=O(\epsilon^{-2} \log n)$ since this is by now a standard trick. $\endgroup$ – Sariel Har-Peled Feb 3 '12 at 23:07
  • 3
    $\begingroup$ To simplify Sariel's answer: Yes. Everyone does this already. $\endgroup$ – Jeffε Feb 4 '12 at 7:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.