<p>In NLP a common problem is that you have vector embeddings of large vocabularies, and you do manipulations on these vector embeddings to compute some result vector, and then you want to find which words in your vocabulary have word embeddings close to the result vector. How can this query be made quickly (and how does it work with a sense of &quot;closeness&quot;?). Of course a naive solution would be to store every vector embedding in some list/array/whatever and just compute the distance between result vector and literally every vector embedding to see which are close. While that works this requires going through every word in the vocabulary. Is there some more efficient way to structure the data and run the query in order to quickly find what vector embeddings are near to the result vector? I assume this is a solved problem and am looking for advice or pointers. I feel like there should be some more structure to the data than the naive solution requires because you should be able to take advantage of, say, the triangle inequality in order to make sure points close to each other sit in some predictable positions in a search tree or something.</p>
<p>This is a self-made problem so please excuse if I'm missing obvious vocabulary (in fact, please advise me on it)!</p>

CC BY-SA 4.0
2023-03-30T01:06:08.760Z
https://en.wikipedia.org/wiki/Nearest_neighbor_search
D.W.
CC BY-SA 4.0
2023-03-30T09:55:40.257Z
@D.W. Perfect Thank you!!
John_Krampf
<ds.algorithms><reference-request><ds.data-structures>
What Data Structure storing points in space for fast lookup of stored points "near" a query point?
John_Krampf
# What Data Structure storing points in space for fast lookup of stored points "near" a query point?

(Asked by: username_0 on 2023-03-29)

In NLP a common problem is that you have vector embeddings of large vocabularies, and you do manipulations on these vector embeddings to compute some result vector, and then you want to find which words in your vocabulary have word embeddings close to the result vector. How can this query be made quickly (and how does it work with a sense of "closeness"?). Of course a naive solution would be to store every vector embedding in some list/array/whatever and just compute the distance between result vector and literally every vector embedding to see which are close. While that works this requires going through every word in the vocabulary. Is there some more efficient way to structure the data and run the query in order to quickly find what vector embeddings are near to the result vector? I assume this is a solved problem and am looking for advice or pointers. I feel like there should be some more structure to the data than the naive solution requires because you should be able to take advantage of, say, the triangle inequality in order to make sure points close to each other sit in some predictable positions in a search tree or something.

This is a self-made problem so please excuse if I'm missing obvious vocabulary (in fact, please advise me on it)!

**Tags:** ds.algorithms, reference-request, ds.data-structures

> **Comments:**
> **username_1**: https://en.wikipedia.org/wiki/Nearest_neighbor_search  
> **username_0**: @username_1 Perfect Thank you!!  

---

## 0 answers

