<p>I think Faiss is exactly what you are looking for. The Github page is <a href="https://github.com/facebookresearch/faiss" rel="nofollow noreferrer">here</a>, if you are interested in the implementation details (this is pretty technical) see <a href="https://arxiv.org/abs/1702.08734" rel="nofollow noreferrer">here</a>, and the tutorial is <a href="https://github.com/facebookresearch/faiss/wiki/Getting-started" rel="nofollow noreferrer">here</a>.</p>
embedding vector search efficient algorithm
<p><strong>background:</strong> I have a machine learning model in which given an object returns an embedding vector with dimension d, the model is trained in a way such that the semantic similarity of two embedding vectors is very close. Now, the verification process is relatively simple, I can take something like the cosine similarity of the two vectors. For recognition, it's a little bit complicated, either I can loop through all the anchor documents and compare the cosine similarity, or use something like kNN (online).</p>
<p><strong>problem:</strong> I have a list of embedding vectors, each vector has a dimension d, with length N. Each vector contains floating-point data.</p>
<p>What will be an efficient data structure + algorithm that can do the following:</p>
<ol>
<li>Can add a new vector with a unique ID to the list efficiently (&lt;= logarithmic complexity)</li>
<li>Search with a random vector in the list, and retrieve top k vectors, such that the Manhattan distance / L1 norm is minimum for those vectors efficiently (hopefully, &lt;= logarithmic complexity).</li>
</ol>
<p><strong>example:</strong></p>
<pre><code>[
 [1., 2., 3.],
 [5., 6., 8.],
 [-11., 2., 31.]
]
</code></pre>
<p><code>k = 2</code>
<code>query = [1.5, 2.5, 3.2]</code>
<code>results:</code></p>
<pre><code>[
 [1., 2., 3.],
 [5., 6., 8.],
]
</code></pre>