Sparse and Dense similarity search

All this time I thought FAISS was an elementary part that later Sparse and Dense similarity search build upon. But I was wrong.

Sparse similarity search methods are simply the ones above, like BM25, TF-IDF, etc., which work on exact word matching with documents. This is good for searching through a document for an exact word. This is very old. It is meant for simple, fast, and scalable use-cases.

Dense similarity search methods are the ones that emphasize similarity in meaning, more than exact matching. Basically, when a model is given a token, it creates an embedding (a high-dimensional vector) that represents that token. Now this embedding holds the MEANING of this token and can then be used for similarity search in this high-dimensional vector space. Surprisingly this includes KNN, ANN, and FAISS.
This is good in cases where a data source uses unstructured keywords or there exist multiple ways to refer to something. Good for medical, legal, and research purposes. It is Context-aware and powerful. But may be slower.

There’s also a nice video I watched a while ago here that discusses distributional semantics that emerge in LLMs.

Hybrid similarity search simply uses both Sparse and Dense search algorithms. It is basically a search algorithm for Vector + Keyword search, and it puts them together using a fusion algorithm, like Weighted Sum (e.g., 70% Dense + 30% sparse) or RRF (Reciprocal Rank Fusion)

Flat Indexing is just KNN (bruh just call it KNN). Apparently a flat index is the data structure used for KNN search (to store distances with all other points).

ANN (Approximate Nearest Neighbours)

• IVF (Inverted File Indexing):
  Divides the entire space into clusters with centroids. So calculates distance of current point with all centroids instead of all other points like KNN.
  Now only focus on the points in the selected cluster and search for the top K similar items
  (This sounds familiar…. I am sure I studied this under a different name)
• HNSW (Hierarchical Navigable Small World):
  The vector space is connected - There are nodes and edges.
  A random starting node is selected. Its distance with the query point is calculated, then its neighbours’. The neighbour who is closest to the query point is selected as the next starting point. This continues until the selected node is closer to the query node than all of its neighbours.
  Problems: If you choose an entry point, all of whose neighbours are away from the query node, it will early stop even though there are better candidates.

FAISS

(Sigh…) This is just a library used to execute these dense algorithms…😒
Whoever named it “Facebook AI Similarity Search” deserves a visit. Who tf names a library as a search algorithm? It is a library that lets people run a lot of similarity searches… Hugely disappointed

Now back to the project 😒