2
$\begingroup$

Are there any open source implementations out there that can efficiently solve the following.

  1. I'm given a fixed set $S$ of $n$-dimensional vectors of size $N$, where $N$ is of the order of a million.

  2. Given an n-dimensional vector $v$, I want to find the top $K$ vectors $w_1,\ldots,w_k$ from $S$, such that the cosine similarity of $v$ and each $w_i$ is maximized.

Here $K$ should be a parameter that I can choose at query time. I know there are various metric data structures that can be used for queries such as these. There's also a paper from Google from last NIPS, where they do this. For example this paper from Google uses an internal library for it:

http://papers.nips.cc/paper/7157-multiscale-quantization-for-fast-similarity-search

$\endgroup$
1
$\begingroup$

If your vectors are dense, you can use a map-reduce code for matrix multiplication (its the best which can be said with the limited information you have provided).

If the vectors are sparse, you can do much better. See

http://www.jmlr.org/papers/volume14/bosagh-zadeh13a/bosagh-zadeh13a.pdf

The authors provide code for their work

$\endgroup$
1
$\begingroup$

What you're describing seems like ideal application for Locality Sensitive Hashing. There exist several libraries that implement nearest neighbor search using LSH.

Some (Python) examples:

$\endgroup$
1
$\begingroup$

Facebook’s FAISS is very good at this kind of thing, and also scalable:

https://code.fb.com/data-infrastructure/faiss-a-library-for-efficient-similarity-search/

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