3
$\begingroup$

As mentioned in the title I am attempting to search through 10,000 vectors with 8000 features each, all in Python. Currently I have the vectors saved in their own directories as pickled numpy arrays. The features were pulled from this deep neural network.

I am new to this space, but I have heard about M-Trees, R-Trees, inverted tables, and hashing. Is any one of them better for such a large number of features?

This implementation needs to be done quite rapidly and is just a prototype, so simplicity is valuable.

Thank you for your help.

$\endgroup$
  • 2
    $\begingroup$ Facebook has a new library, but it's not wise to perform similarity search on such high dimensional spaces with a common metric like the Euclidean distance. stats.stackexchange.com/questions/99171/… $\endgroup$ – Emre Jul 31 '17 at 15:17
  • $\begingroup$ @Emre, yes. I saw their library however they mention on the wiki that the number of dimensions should be in the range of "a few 10s to 100s". $\endgroup$ – Michael Vander Meiden Jul 31 '17 at 16:05
  • 1
    $\begingroup$ For good reason. $\endgroup$ – Emre Jul 31 '17 at 16:06
  • $\begingroup$ @Emre, why is using L2 distance not recommended for this number of dimension? Is that based on computation time, accuracy, or something else? $\endgroup$ – Michael Vander Meiden Jul 31 '17 at 19:45
  • 2
    $\begingroup$ Based on the concentration of measure. I linked to an explanation already. $\endgroup$ – Emre Jul 31 '17 at 20:16
2
$\begingroup$

There are two main paths:

  1. Load all vectors into memory. If you are able to load vectors into memory, then you might be able to search the space with "clever" brute force. One such method is found in this paper.

  2. Keep vectors on disk. If you follow this path, then you have to index the vectors. You are basically building a search engine. Common open source search engines are: Apache Solr and Elasticsearch

It also depends on what kind of what kind of search is needed. A working definition of "close" vector is needed. The most common definitions of "close" vectors can be found here.

Fais is a new library for efficient similarity search of vectors. It is designed for many vectors (> 1,000,000) each being relatively small (10s to 100s of dimensions). It may or may not scale to your problem. If it does not scale because of high dimensionality, you can reduce dimensionality with Principal component analysis (PCA) or t-SNE.

$\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.