<p>Andoni and Indyk presented a paper in FOCS 2006: <a href="http://www.mit.edu/~andoni/papers/cSquared.pdf" rel="nofollow">Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions</a>. 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.</p>

<p>Is it possible to first preprocess with some dimension reduction technique and then apply the same Andoni / Indyk algorithm?</p>

<p>For example, we could apply a <a href="http://arxiv.org/abs/1012.1577" rel="nofollow">Johnson-Lindenstrauss Transform</a>. 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&#177; \epsilon$." </p>

<p>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?</p>

<p>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.</p>

<h3> More detail: </h3>

<p>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)$."</p>

<p><em>At first this made me think that another dimension reduction would be redundant.</em></p>

<p><strong>However</strong>, 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 <a href="http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.38.249" rel="nofollow">IM98</a>). </p>

<p>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 <em>another</em> 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) &lt; O(dn^\rho) $ when $d$ is large.</p>

CC BY-SA 3.0
2012-02-03T01:17:11.417Z
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.
vzn
CC BY-SA 3.0
2012-02-03T04:59:18.757Z
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?
Joe
CC BY-SA 3.0
2012-02-03T05:28:56.560Z
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.
vzn
CC BY-SA 3.0
2012-02-03T06:50:19.483Z
I'm interested in a theoretical result.
Joe
CC BY-SA 3.0
2012-02-03T16:25:25.720Z
you're being too vague on the application or data type. the papers refer to particular applications. which one is it? is it in the list? in theory yes it will work :p
vzn
CC BY-SA 3.0
2012-02-03T17:37:46.040Z
The idea is to improve the bounds in Andoni and Indyk's algorithm by preprocessing the points first. The data (points in high-dimensional Euclidean space) and the application ($c$-approximate nearest neighbor) remain the same.
Joe
CC BY-SA 3.0
2012-02-03T23:07:26.033Z
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.
Sariel Har-Peled
CC BY-SA 3.0
2012-02-04T07:29:46.893Z
To simplify Sariel's answer: Yes. Everyone does this already.
Jeffε
CC BY-SA 3.0
2012-02-06T19:29:28.683Z
@JɛﬀE I added a lot more detail to the question. Is your answer still the same?
Joe
<ds.algorithms><reference-request><cg.comp-geom>
Can we reduce dimensions before applying high dimensional approximate nearest neighbor algorithms?
Joe
# Can we reduce dimensions before applying high dimensional approximate nearest neighbor algorithms?

(Asked by: username_0 on 2012-02-03)

Andoni and Indyk presented a paper in FOCS 2006: [Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions](http://www.mit.edu/~andoni/papers/cSquared.pdf). 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](http://arxiv.org/abs/1012.1577). 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](http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.38.249)).

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.

**Tags:** ds.algorithms, reference-request, cg.comp-geom

> **Comments:**
> **username_1**: 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.  
> **username_0**: 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?  
> **username_1**: 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.  
> **username_0**: I'm interested in a theoretical result.  
> **username_1**: you're being too vague on the application or data type. the papers refer to particular applications. which one is it? is it in the list? in theory yes it will work :p  
> **username_0**: The idea is to improve the bounds in Andoni and Indyk's algorithm by preprocessing the points first. The data (points in high-dimensional Euclidean space) and the application ($c$-approximate nearest neighbor) remain the same.  
> **username_2**: 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.  
> **username_3**: To simplify Sariel's answer: Yes. Everyone does this already.  
> **username_0**: @JɛﬀE I added a lot more detail to the question. Is your answer still the same?  

---

## 0 answers

