VectorSearch

Question 1

What is K-Approximate Nearest Neighbor (K-ANN)?

Answer 1

Algorithm to find K nearest elements to a query vector in a large dataset

Question 2

Why are approximate algorithms (ANNS) used instead of exact methods?

Answer 2

Because exact methods become computationally expensive as dataset size and vector dimensionality increase

Question 3

What is HNSW?

Answer 3

Hierarchical Navigable Small World - an ANNS algorithm offering logarithmic search complexity based on navigable small-world graphs

Question 4

What is a skip list?

Answer 4

A probabilistic data structure using additional levels of pointers to speed up search insertion and deletion in an ordered list

Question 5

What are the three main advantages of skip lists?

Answer 5

1) Logarithmic search time 2) Efficient insertion/deletion 3) Low average memory usage per node

Question 6

What are the two main disadvantages of skip lists?

Answer 6

1) Higher memory overhead from additional pointers 2) Complex theoretical analysis

Question 7

How is the maximum level assigned to elements in HNSW?

Answer 7

Using an exponentially decaying probability distribution: ⌊−ln(unif(0 1)) ∗ mL)⌋

Question 8

What are the two phases of HNSW insertion?

Answer 8

1) Zoom-out: traverse graph to find nearest element 2) Zoom-in: expand search to find more nearest neighbors

Question 9

How does K-ANN search work in HNSW?

Answer 9

Start from top layer find closest neighbor pass to lower layer and at layer 0 find ef candidates

Question 10

What are the main limitations of HNSW?

Answer 10

1) Requires processing entire dataset before queries 2) High RAM usage 3) Difficult to implement distributed search

Question 11

What is SPANN?

Answer 11

Scalable Partitioned Approximate Nearest Neighbor - a hybrid memory-disk indexing system for ANNS

Question 12

What is the basic structure of SPANN?

Answer 12

Data vectors divided into posting lists each associated with a centroid centroids stored in memory as coarse-grained index

Question 13

What are the three steps in SPANN’s balanced hierarchical clustering?

Answer 13

1) Initial clustering 2) Iterative subdivision 3) Final assignment

Question 14

Why does SPANN use multi-cluster assignment?

Answer 14

To address the boundary issue where nearby vectors may not be effectively represented by a single centroid

Question 15

What are the two main costs of duplication in SPANN?

Answer 15

1) Higher disk usage 2) Potential disk read redundancy

Question 16

What are the main advantages of SPANN?

Answer 16

High scalability low query latency reduced memory cost

Question 17

What are the main limitations of SPANN?

Answer 17

High disk cost due to data replication data freshness not guaranteed by default

Question 18

How does SPANN determine which posting lists to fetch during search?

Answer 18

It finds the closest centroid to query and selects lists whose centroids are almost as close

Question 19

What is the purpose of the RNG rule in SPANN?

Answer 19

To reduce similarity between neighboring posting lists ensuring duplicated vectors are distributed uniformly

Question 20

What is the boundary issue in SPANN?

Answer 20

When nearby vectors may not be effectively represented by the centroid of a single list