<p>What you're looking for is a procedure to do near-neighbor searching in a high dimensional Euclidean space, or do dimensionality reduction prior to doing such a near neighbor search. </p>

<p>There are two approaches that are likely to help:</p>

<ul>
<li>Use a native near-neighbor search procedure that works in high dimensions. <a href="http://en.wikipedia.org/wiki/Locality-sensitive_hashing">Locality-sensitive hashing</a> is a popular choice in this regard. </li>
<li>Apply dimensionality reduction, and then use a technique that works for fewer dimensions. In this case, you should look at the <a href="http://www.cs.umd.edu/~mount/ANN/">ANN near-neighbor library</a>, and also look into using the <a href="http://en.wikipedia.org/wiki/Johnson%E2%80%93Lindenstrauss_lemma">Johnson-Lindenstrauss transform</a> for dimensionality reduction (or possibly even PCA to reduce dimensions). </li>
</ul>

<p>(warning - self promotion alert: <a href="http://www.cs.utah.edu/~suresh/papers/jlx/jlx.pdf">I have a paper</a> that describes different implementations of Johnson-Lindenstrauss and how they compare)</p>

CC BY-SA 3.0
2011-05-30T19:18:08.113Z
2011-05-30T19:18:08.113Z
Suresh Venkat
<p>I want to compute Euclidian distance between similar vectors in a database (SQLite).
So each column in the database is a value from my vector.</p>

<p>The first problem appears, I have a large number of values that I first need to reduce to fit a reasonable number of rows (&lt;50) since the original data have thousands of columns.
I have also thought of storing a blob, load it in memory and do my computations ?</p>

<p>Since I am trying to find the best matches (similarity mesure), I am currently filtering the database by applying a threshold for each value. Applying a filter for a small number of column is feasible, doing this for many columns is too time consuming.</p>

<p>Sqlite has a RTree module limited to 5 dimensions (11 columns). But it is not the filtering that I want.</p>

<p>What is the best compromise or technique/algorithm to sort and compare vectors using a database ?</p>

<p>Thank you</p>

<ds.algorithms><cg.comp-geom><near-neighbors>
Compare similar N-Dimensional vector in a database
Kirell
# Compare similar N-Dimensional vector in a database

(Asked by: username_0 on 2011-05-30)

I want to compute Euclidian distance between similar vectors in a database (SQLite).
So each column in the database is a value from my vector.

The first problem appears, I have a large number of values that I first need to reduce to fit a reasonable number of rows (<50) since the original data have thousands of columns.
I have also thought of storing a blob, load it in memory and do my computations ?

Since I am trying to find the best matches (similarity mesure), I am currently filtering the database by applying a threshold for each value. Applying a filter for a small number of column is feasible, doing this for many columns is too time consuming.

Sqlite has a RTree module limited to 5 dimensions (11 columns). But it is not the filtering that I want.

What is the best compromise or technique/algorithm to sort and compare vectors using a database ?

Thank you

**Tags:** ds.algorithms, cg.comp-geom, near-neighbors


---

## 1 answers

### Answer by username_1 on 2011-05-30. Score: 5 | Accepted answer

What you're looking for is a procedure to do near-neighbor searching in a high dimensional Euclidean space, or do dimensionality reduction prior to doing such a near neighbor search.

There are two approaches that are likely to help:

* Use a native near-neighbor search procedure that works in high dimensions. [Locality-sensitive hashing](http://en.wikipedia.org/wiki/Locality-sensitive_hashing) is a popular choice in this regard.
* Apply dimensionality reduction, and then use a technique that works for fewer dimensions. In this case, you should look at the [ANN near-neighbor library](http://www.cs.umd.edu/~mount/ANN/), and also look into using the [Johnson-Lindenstrauss transform](http://en.wikipedia.org/wiki/Johnson%E2%80%93Lindenstrauss_lemma) for dimensionality reduction (or possibly even PCA to reduce dimensions).

(warning - self promotion alert: [I have a paper](http://www.cs.utah.edu/~suresh/papers/jlx/jlx.pdf) that describes different implementations of Johnson-Lindenstrauss and how they compare)


---

