Skip to main content
Computer Science

Return to Answer

added 97 characters in body
Source Link
SilvioM
SilvioM
  • 1.3k
  • 4
  • 13

I don't think any exact approach to solve this problem in $O(N \log N)$ exists. You can look for Approximate Nearest Neighbors search methods with theoretical logarithmic complexity for a single query (e.g. HNSW, NSG, etc). However these guarantees do not hold in practice because you lack the hypothesis on which the proofs are based. In practice you can regulate the trade-off between accuracy and speed of the search through some parameters (e.g. ef_search in HNSW).

These approaches are very fast and effective in practice and, by tuning the search parameters you can easily achieve accuracies near $100\%$. They are really fast because they can find the approximate $k$NN by scanning a small percentage of the dataset (e.g. $<1\%$). Also, they allow to submit many queries at the same time and they benefit from handling multiple queries thanks to techniques like for instance vectorization.

I suggest you to try FAISS (Facebook AI Similarity Search) which has many methods for ANN search (also methods like IVF index or hash-based approaches or GPU indexes that are very fast on GPUs).

Note that the guarantees hold for distance metrics, while inner product is not a distance. However, very often it also works in practice and it is implemented as one possible metric to compare vectors.

I don't think any exact approach to solve this problem in $O(N \log N)$ exists. You can look for Approximate Nearest Neighbors search methods with theoretical logarithmic complexity for a single query (e.g. HNSW, NSG, etc). However these guarantees do not hold in practice because you lack the hypothesis on which the proofs are based. In practice you can regulate the trade-off between accuracy and speed of the search through some parameters (e.g. ef_search in HNSW).

These approaches are very fast and effective in practice and, by tuning the search parameters you can easily achieve accuracies near $100\%$. They are really fast because they can find the approximate $k$NN by scanning a small percentage of the dataset (e.g. $<1\%$). Also, they allow to submit many queries at the same time and they benefit from handling multiple queries thanks to techniques like for instance vectorization.

I suggest you to try FAISS (Facebook AI Similarity Search) which has many methods for ANN search.

Note that the guarantees hold for distance metrics, while inner product is not a distance. However, very often it also works in practice and it is implemented as one possible metric to compare vectors.

I don't think any exact approach to solve this problem in $O(N \log N)$ exists. You can look for Approximate Nearest Neighbors search methods with theoretical logarithmic complexity for a single query (e.g. HNSW, NSG, etc). However these guarantees do not hold in practice because you lack the hypothesis on which the proofs are based. In practice you can regulate the trade-off between accuracy and speed of the search through some parameters (e.g. ef_search in HNSW).

These approaches are very fast and effective in practice and, by tuning the search parameters you can easily achieve accuracies near $100\%$. They are really fast because they can find the approximate $k$NN by scanning a small percentage of the dataset (e.g. $<1\%$). Also, they allow to submit many queries at the same time and they benefit from handling multiple queries thanks to techniques like for instance vectorization.

I suggest you to try FAISS (Facebook AI Similarity Search) which has many methods for ANN search (also methods like IVF index or hash-based approaches or GPU indexes that are very fast on GPUs).

Note that the guarantees hold for distance metrics, while inner product is not a distance. However, very often it also works in practice and it is implemented as one possible metric to compare vectors.

Source Link
SilvioM
SilvioM
  • 1.3k
  • 4
  • 13

I don't think any exact approach to solve this problem in $O(N \log N)$ exists. You can look for Approximate Nearest Neighbors search methods with theoretical logarithmic complexity for a single query (e.g. HNSW, NSG, etc). However these guarantees do not hold in practice because you lack the hypothesis on which the proofs are based. In practice you can regulate the trade-off between accuracy and speed of the search through some parameters (e.g. ef_search in HNSW).

These approaches are very fast and effective in practice and, by tuning the search parameters you can easily achieve accuracies near $100\%$. They are really fast because they can find the approximate $k$NN by scanning a small percentage of the dataset (e.g. $<1\%$). Also, they allow to submit many queries at the same time and they benefit from handling multiple queries thanks to techniques like for instance vectorization.

I suggest you to try FAISS (Facebook AI Similarity Search) which has many methods for ANN search.

Note that the guarantees hold for distance metrics, while inner product is not a distance. However, very often it also works in practice and it is implemented as one possible metric to compare vectors.