HNSW — greedy descent qua các tầng

HNSW — greedy descent qua các tầng A workflow diagram generated by Archify. 01 / Tầng trên (2–5) — ~4.100 điểm 02 / Tầng 1 — ~62.500 điểm 03 / Tầng 0 — 1.000.000 điểm EX / Chỗ greedy hết bảo đảm Định vị thô — ef = 1 Tinh chỉnh — ef thật Điểm vào · cố định ở tầng đỉnh · Tầng trên (2–5) — ~4.100 điểm › Định vị thô — ef = 1 Điểm vào cố định ở tầng đỉnh Greedy ef = 1 · bước dài — đi xa nhanh · Tầng trên (2–5) — ~4.100 điểm › Định vị thô — ef = 1 · P(l ≥ j) = (1/M)^j Greedy ef = 1 bước dài — đi xa nhanh P(l ≥ j) = (1/M)^j Greedy ef = 1 · tụt tại điểm cực tiểu · Tầng 1 — ~62.500 điểm › Định vị thô — ef = 1 Greedy ef = 1 tụt tại điểm cực tiểu SEARCH-LAYER ef = 128 · beam search, ef rộng · Tầng 0 — 1.000.000 điểm › Tinh chỉnh — ef thật · tầng 0: 2M cạnh/node SEARCH-LAYER ef = 128 beam search, ef rộng tầng 0: 2M cạnh/node Top-k · bắt buộc ef ≥ k · Tầng 0 — 1.000.000 điểm › Tinh chỉnh — ef thật Top-k bắt buộc ef ≥ k Node tombstone · đi qua, không trả về · Chỗ greedy hết bảo đảm › Tinh chỉnh — ef thật Node tombstone đi qua, không trả về Filter → đồ thị rời rạc · greedy mất bảo đảm · Chỗ greedy hết bảo đảm › Tinh chỉnh — ef thật Filter → đồ thị rời rạc greedy mất bảo đảm tụt xuống tầng 0 tụt 1 tầng node đã xoá mềm Legend Kết quả Bước tìm kiếm Chỗ vỡ Điểm vào

Vì sao có tầng — tính bằng tay

  • • Tầng của x: l = ⌊−ln(U(0,1)) · mL⌋ với mL = 1/ln M
  • • P(l ≥ j) = (1/M)^j → mỗi tầng lên cao thưa đi đúng M lần
  • • M = 16, N = 1M → 1M / 62.500 / 3.906 / 244 / 15 / ~1

Ba núm, hai thời điểm

  • • M — build, bất biến; RAM ≈ M × 8–10 byte/vector
  • • efConstruction — build, chỉ trả giá một lần
  • • ef — runtime, núm recall duy nhất không cần build lại
  • • ef là độ rộng vùng giữ mở, không phải số node sẽ thăm

Cắt tỉa heuristic: chỗ không được cắt góc

  • • Lấy M cạnh gần nhất làm đồ thị vỡ thành các cụm rời
  • • Bỏ ứng viên e nếu ∃ r đã chọn với d(e, r) < d(e, q)
  • • Nhờ vậy cạnh dài liên cụm được giữ → đồ thị vẫn navigable