VDBMS Vector Databases

Question 1

Semantic search

Answer 1

Query Embedding -> Nearest Neighbor Search

Question 2

Nearest Neighbor queries: naive method

Answer 2

*full scan
*sort
*top-k
*Inefficient

Question 3

Nearest Neighbor queries: Index-based method

Answer 3

• Build a spatial index on embeddings
  and use kNN search.
  *Curse of dimensionality

Question 4

definition of RAG

Answer 4

Retrieval Augmented Generation

Question 5

what does Retrieval Augmented Generation do when given a query

Answer 5

*Create a query embedding
*Run an approximate nearest neighbor (ANN) query
to find the most relevant documents
*With an appropriate prompt, feed the documents
through a generative AI model to get the final
answer

Question 6

Vector Indexing

Answer 6

• A way to index multidimensional data points
• Given a query point, find the nearest data point
• Traditional spatial indexes (based on Euclidean
  distance) work for low-dimensional data
• As number of dimensions increases, all points
  become equally near

Question 7

Locality Sensitive Hashing (LSH)

Answer 7

• Traditional hashing is good for point queries with
  exact match
• Locality Sensitive Hashing (LSH) works for proximity
  queries

Question 8

Product Quantization (PQ) Operations

Answer 8

*Break down a big vector into subvectors
*Quantize the value of each subvector - Reduce the size of each vector
*Store a list of vector IDs (record IDs) and their corresponding quantized vector
*For a query vector (q), do the same quantization
*Compute the distances to the quantized vectors and the find the nearest one

Question 9

Navigable Small World (NSW)
basic concept

Answer 9

*Connect each data point to its
nearest neighbors
*Connect each data point to a few
faraway neighbors
*Search: Follow the edges to the
target point

Question 10

Hierarchical Navigable Small World (HNSW)
basic concept

Answer 10

*Create a hierarchy of graphs
*Each vertex is elevated to the higher level with a probability
*Search starts at the highest level and goes to the next level when the search converges

Question 11

Key indexing tools:

Answer 11

LSH, HNSW, Product Quantization (PQ)

Question 12

Vector DBs integrate what

Answer 12

embedding storage, ANN search, and RAG