1
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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 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, and also look into using the Johnson-Lindenstrauss transform for dimensionality reduction (or possibly even PCA to reduce dimensions).

(warning - self promotion alert: I have a paper that describes different implementations of Johnson-Lindenstrauss and how they compare)

| cite | improve this answer | |
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.