Bài 6: Chỉ mục Đồ thị HNSW (Hierarchical Navigable Small World)

Trong số các giải thuật tìm kiếm lân cận gần nhất xấp xỉ (ANN), các chỉ mục dựa trên cấu trúc đồ thị luôn đạt tỷ lệ Recall cao nhất và thời gian truy vấn Latency cực kỳ ấn tượng. Đại diện ưu tú và được sử dụng rộng rãi nhất hiện nay chính là HNSW (Hierarchical Navigable Small World).

Bài học này sẽ đưa bạn khám phá nguồn gốc lý thuyết của HNSW từ cấu trúc Skip-list, cơ chế phân tầng đồ thị thông minh, giải thuật định tuyến tham lam (Greedy Search) và các chiến lược loại bỏ liên kết thừa để tối ưu bộ nhớ.

6.1 Sự tiến hóa từ cấu trúc dữ liệu Skip-List lên Đồ thị

Để hiểu rõ HNSW, trước tiên hãy xem xét cấu trúc Skip-List trong không gian 1 chiều. Một danh sách liên kết thông thường yêu cầu thời gian duyệt $O(N)$ để tìm kiếm phần tử. Skip-list khắc phục điều này bằng cách tạo ra các tầng liên kết "nhảy cóc" bên trên. Tầng càng cao thì số lượng phần tử càng thưa thớt, cho phép thuật toán đi những bước dài trước để thu hẹp phạm vi, sau đó đi xuống tầng dưới để dò chi tiết. Kết quả là thời gian tìm kiếm rút xuống còn $O(\log N)$.

HNSW áp dụng nguyên lý phân tầng này nhưng đưa lên không gian đa chiều của các proximity graphs (đồ thị lân cận). Thay vì các liên kết nhảy cóc tuyến tính trên trục số 1D, các liên kết của HNSW là các cạnh đồ thị kết nối các vector gần nhau trong không gian đa chiều, giúp dẫn đường cho thuật toán di chuyển nhanh tới khu vực chứa kết quả.

// Minh họa tư duy duyệt Skip-list phân tầng 1D
function searchSkipList(list, target) {
  let curr = list.head;
  let level = list.maxLevel - 1;
  
  // Duyệt từ tầng cao xuống tầng thấp
  while (level >= 0) {
    while (curr.next[level] && curr.next[level].value < target) {
      curr = curr.next[level]; // Di chuyển ngang ở tầng cao
    }
    level--; // Rớt xuống tầng dưới
  }
  return curr.next[0] && curr.next[0].value === target ? curr.next[0] : null;
}

6.2 Cấu trúc đồ thị phân tầng (Hierarchical Graph Layout)

Cấu trúc HNSW bao gồm nhiều lớp đồ thị được xếp tầng lên nhau:

• Tầng Đáy (Layer 0): Chứa toàn bộ các vector trong cơ sở dữ liệu. Đồ thị ở tầng này cực kỳ dày đặc và kết nối chặt chẽ để đảm bảo không bỏ sót bất kỳ node nào.
• Các Tầng Trên (Layer 1 đến Layer L): Chứa một tập con thưa thớt của các vector. Mỗi node mới chèn vào sẽ được chỉ định ngẫu nhiên một tầng cao nhất $l$ theo phân phối hình học:

Trong đó, $\text{uniform}(0, 1)$ là số ngẫu nhiên từ $0$ đến $1$, và $m_L$ là tham số điều phối phân bổ. Tầng càng cao thì khoảng cách địa lý giữa các node liên kết càng xa nhau, đóng vai trò như các xa lộ định hướng tầm xa.

6.3 Thuật toán duyệt đồ thị (Greedy Search)

Thuật toán định tuyến tìm kiếm trên HNSW di chuyển theo cơ chế Tham lam cục bộ (Greedy Routing):

1. Bắt đầu tại điểm vào (Enter Point) ở tầng cao nhất hiện tại.
2. Tại tầng hiện tại, tính khoảng cách từ vector truy vấn $\mathbf{q}$ tới tất cả các node láng giềng của node hiện tại.
3. Di chuyển sang node láng giềng có khoảng cách gần nhất. Lặp lại cho đến khi không tìm thấy láng giềng nào gần $\mathbf{q}$ hơn node hiện tại (đạt cực trị địa phương - local minimum).
4. Lấy node cực trị địa phương này làm điểm vào cho tầng ngay bên dưới, và lặp lại bước 2. Khi chạm xuống Layer 0, thuật toán sẽ thu thập danh sách Top K kết quả tốt nhất.

// Tìm kiếm tham lam trên một tầng đồ thị đơn lẻ
function searchLayerGreedy(query, enterNode, layer) {
  let currNode = enterNode;
  let currDist = calculateDistance(query, currNode.vector);
  let changed = true;
  
  while (changed) {
    changed = false;
    // Duyệt láng giềng của node hiện tại ở tầng 'layer'
    for (const neighborId of currNode.neighbors[layer]) {
      const neighbor = nodes.get(neighborId);
      const dist = calculateDistance(query, neighbor.vector);
      if (dist < currDist) {
        currDist = dist;
        currNode = neighbor;
        changed = true; // Tiếp tục định tuyến sang node tốt hơn
      }
    }
  }
  return currNode; // Đạt cực trị địa phương
}

6.4 Thuật toán chèn Node mới và Heuristic chọn láng giềng kết nối

Khi chèn một vector mới vào đồ thị HNSW, chúng ta cần tìm láng giềng gần nhất cho nó để thực hiện kết nối cạnh hai chiều. Hai tham số điều phối cốt lõi là:

• $M$ (Max Connections): Số lượng liên kết tối đa của mỗi node trên mỗi tầng. Khi số láng giềng vượt quá $M$, thuật toán phải cắt bớt các liên kết kém chất lượng hơn.
• $efConstruction$ (Size of candidate list): Độ sâu hàng đợi ứng viên khi xây dựng đồ thị. Tham số này càng lớn thì đồ thị xây dựng càng chính xác nhưng thời gian index sẽ lâu hơn.

Thay vì chỉ chọn đơn thuần $M$ láng giềng gần nhất tuyệt đối (có thể dẫn đến các cụm node bị cô lập hoặc liên kết quá cục bộ), HNSW áp dụng giải thuật Heuristic Selection: Chọn các láng giềng đa dạng về hướng không gian để đảm bảo đồ thị luôn kết nối đa chiều.

// Mô phỏng cơ chế cập nhật láng giềng lân cận đa hướng
function updateNeighbors(node, newNeighbor, layer, maxM) {
  node.neighbors[layer].add(newNeighbor.id);
  
  if (node.neighbors[layer].size > maxM) {
    // Thu gọn liên kết bằng cách ưu tiên các láng giềng đa hướng (Heuristic đơn giản)
    const sorted = Array.from(node.neighbors[layer])
      .map(id => ({ id, dist: getDistance(node.id, id) }))
      .sort((a, b) => a.dist - b.dist);
      
    // Giữ lại maxM phần tử gần nhất
    node.neighbors[layer] = new Set(sorted.slice(0, maxM).map(x => x.id));
  }
}

6.5 Phân tích hiệu năng và Chi phí bộ nhớ của HNSW

Nhờ cấu trúc định tuyến phân tầng bỏ qua phần lớn dữ liệu không liên quan, HNSW đạt thời gian tìm kiếm trung bình cực nhanh:

Độ trễ Latency của HNSW thường chỉ dao động từ $1 - 10$ mili-giây đối với hàng triệu vector, đồng thời duy trì Recall cực cao (trên $98\%$).

Bảng so sánh hiệu năng các loại cấu trúc đồ thị chỉ mục:

6.6 Thực hành: Duyệt đồ thị HNSW từng bước

Demo dưới đây dựng một đồ thị HNSW thật (dùng đúng lớp HNSWIndex của vdb-engine.js) từ 30 điểm 2D ngẫu nhiên với $M=4$, $efConstruction=16$ — số nhỏ để đồ thị còn đơn giản, dễ nhìn. Các cạnh Layer 0 (đồ thị nền dày đặc, Mục 6.2) được vẽ mờ màu xám, còn các cạnh Layer 1 trở lên (các "xa lộ" thưa thớt, Mục 6.1) được tô màu tím sáng — node nào tồn tại ở tầng cao hơn cũng được vẽ to hơn để thấy rõ vai trò node trung chuyển. Bấm "▶ Bước tiếp theo" để duyệt từng bước Greedy Search y hệt giải thuật ở Mục 6.3: bắt đầu tại điểm vào (Enter Point) ở tầng cao nhất, di chuyển tham lam sang láng giềng gần hơn, rớt tầng khi kẹt cực trị địa phương, cho tới khi chạm Layer 0 — lúc đó demo gọi search() chính thức để đối chiếu kết quả Top-K:

import { HNSWIndex, calculateDistance } from './vdb-engine.js';

const CANVAS_W = 640, CANVAS_H = 320, PADDING = 28, NUM_POINTS = 30;

function randomPoint() {
  return [PADDING + Math.random() * (CANVAS_W - 2 * PADDING), PADDING + Math.random() * (CANVAS_H - 2 * PADDING)];
}

// Dung Index THAT: M=4, efConstruction=16 - nho de do thi con don gian de quan sat
let points, index, query, walk;

function buildIndex() {
  points = Array.from({ length: NUM_POINTS }, (_, i) => ({ id: i, vector: randomPoint() }));
  index = new HNSWIndex(4, 16, 'euclidean');
  for (const p of points) index.insert(p.id, p.vector);
}

// Khoi tao trang thai duyet: bat dau tai enterPointId, o tang maxLayer
function initWalk() {
  const startId = index.enterPointId;
  const startDist = calculateDistance(query, index.nodes[startId].vector, index.metric);
  walk = { currentId: startId, currentLayer: index.maxLayer, currentDist: startDist, trail: [{ id: startId, layer: index.maxLayer }], done: false, results: null };
}

// Mot buoc Greedy Search - phong theo dung logic cua HNSWIndex.search():
// tai moi tang, di chuyen sang lang gieng gan hon; het cai thien thi rot tang;
// den Layer 0 thi goi search() that de lay Top-K chinh thuc.
function stepWalk() {
  if (!walk || walk.done) return;
  const node = index.nodes[walk.currentId];
  const neighbors = node.layers[walk.currentLayer] || [];

  let bestId = null, bestDist = walk.currentDist;
  for (const neighborId of neighbors) {
    const d = calculateDistance(query, index.nodes[neighborId].vector, index.metric);
    if (d < bestDist) { bestDist = d; bestId = neighborId; }
  }

  if (bestId !== null) {
    // Tim thay lang gieng gan hon -> di chuyen ngang tai tang hien tai
    walk.currentId = bestId;
    walk.currentDist = bestDist;
    walk.trail.push({ id: bestId, layer: walk.currentLayer });
  } else if (walk.currentLayer > 0) {
    // Cuc tri dia phuong tai tang nay -> rot xuong tang duoi
    walk.currentLayer -= 1;
    walk.trail.push({ id: walk.currentId, layer: walk.currentLayer });
  } else {
    // Da cham Layer 0 va hoi tu -> doi chieu voi search() CHINH THUC
    walk.results = index.search(query, 3, 32);
    walk.done = true;
  }
}

// render(ctx) ve: canh Layer 0 mo xam, canh Layer 1+ mau tim (#a855f7, node
// to hon), duong di walk.trail mau indigo (#4f46e5), node hien tai khoanh
// cyan (#06b6d4), diem truy van hinh kim cuong vang, Top-K cuoi cung khoanh
// xanh la khi walk.done === true.