EasyDeepLearn

HNSW — how does it work?

hard

Answer

  • Hierarchical multi-layer graph.
  • Top layer: sparse long-range edges.
  • Lower layers: denser short-range.
  • Search: start at top, greedy traversal toward query, descend one layer, refine.
  • Insertion: probabilistically assign layer (exponential decay), connect to M nearest neighbors per layer.
  • Log-time search on average.
  • Trade-off knobs: M (neighbors per node), efconstruction  /  efsearch\mathrm{ef}_{\mathrm{construction}}\; / \;\mathrm{ef}_{\mathrm{search}} (search-time exploration).
Check yourself — multiple choice
  • Random
  • Hierarchical graph: sparse top layer for long-range, dense bottom for local; greedy descent search; M  +  efconstruction  +  efsearchM\; + \;\mathrm{ef}_{\mathrm{construction}}\; + \;\mathrm{ef}_{\mathrm{search}} tuning knobs; log-time
  • Same as k-d tree
  • Not real

HNSW: hierarchical navigable graph; log-time ANN; M / ef parameters.

#applications#similarity

Practise Unsupervised Learning

214 interview questions in this topic.

Read the lessonFlashcardsTake the quiz

Related questions