Bài 5: Chỉ mục IVF (Inverted File Index) & Phân hoạch Voronoi

Khi số lượng vector nhúng trong cơ sở dữ liệu tăng lên hàng triệu hoặc hàng tỷ bản ghi, việc quét tuyến tính (Flat / Brute-force scan) để so sánh khoảng cách từng vector với vector truy vấn sẽ mất hàng giây CPU. Để giải quyết vấn đề quy mô lớn này, chúng ta phải chuyển sang sử dụng giải thuật Tìm kiếm xấp xỉ lân cận gần nhất (Approximate Nearest Neighbors - ANN).

Bài học này sẽ hướng dẫn bạn chi tiết cấu trúc chỉ mục phổ biến hàng đầu trong các Vector DB: Chỉ mục danh sách đảo ngược (Inverted File Index - IVF), cơ chế toán học đứng sau việc phân hoạch không gian Voronoi và cách tối ưu hóa Recall/Latency bằng các tham số cấu hình.

5.1 ANN Search & Tại sao cần phân hoạch không gian Voronoi

Ý tưởng cốt lõi của tìm kiếm xấp xỉ ANN là: Thay vì so khớp vector truy vấn với toàn bộ kho cơ sở dữ liệu, chúng ta chia nhỏ không gian đa chiều thành các khu vực riêng biệt và chỉ quét chi tiết trong các khu vực nằm gần vector truy vấn nhất.

Phương pháp phân mảnh không gian kinh điển nhất trong hình học đa chiều là Phân hoạch Voronoi (Voronoi Partitioning). Cho trước một danh sách $k$ điểm mốc gọi là các Centroids $\{\mathbf{c}_1, \mathbf{c}_2, \dots, \mathbf{c}_k\}$, mỗi centroid sẽ cai quản một vùng tế bào Voronoi (Voronoi Cell). Vùng tế bào Voronoi $V_i$ chứa mọi điểm trong không gian có vị trí gần centroid $\mathbf{c}_i$ nhất so với bất kỳ centroid nào khác:

5.2 Thuật toán K-Means Clustering trong không gian Metric

Để tìm được các centroids tối ưu chia đều mật độ không gian vector, chúng ta áp dụng thuật toán phân cụm K-Means Clustering.

Thuật toán hoạt động qua 2 bước lặp tuần hoàn cho đến khi hội tụ:

1. Bước gán (Assignment Step): Tính khoảng cách từ mỗi vector trong bộ dữ liệu đến tất cả centroids hiện tại, gán vector đó vào cụm $S_j$ của centroid gần nhất.
2. Bước cập nhật (Update Step): Tính toán lại tọa độ của từng centroid $\mathbf{c}_j$ bằng cách lấy trung bình cộng tọa độ của tất cả các vector đã được gán cho cụm đó:

// Hàm tối ưu hóa K-Means tối giản
function kMeans(vectors, k, iterations = 10) {
  let centroids = vectors.slice(0, k).map(v => [...v]); // Khởi tạo ngẫu nhiên
  
  for (let iter = 0; iter < iterations; iter++) {
    const buckets = Array.from({ length: k }, () => []);
    
    // 1. Phân phối vector về centroid gần nhất
    for (const vec of vectors) {
      let minDist = Infinity, bestIdx = 0;
      for (let i = 0; i < k; i++) {
        const dist = vec.reduce((sum, val, d) => sum + Math.pow(val - centroids[i][d], 2), 0);
        if (dist < minDist) {
          minDist = dist;
          bestIdx = i;
        }
      }
      buckets[bestIdx].push(vec);
    }
    
    // 2. Tính toán lại tọa độ centroid
    for (let i = 0; i < k; i++) {
      if (buckets[i].length === 0) continue;
      const newCentroid = new Array(centroids[0].length).fill(0);
      for (const vec of buckets[i]) {
        vec.forEach((val, d) => newCentroid[d] += val);
      }
      centroids[i] = newCentroid.map(val => val / buckets[i].length);
    }
  }
  return centroids;
}

5.3 Cấu trúc danh sách đảo ngược (Inverted Lists)

Sau khi phân cụm không gian thành $k$ centroids, làm sao để lưu trữ hiệu quả các vector thuộc từng cụm? Chúng ta sử dụng cấu trúc Danh sách đảo ngược (Inverted Lists - IVF).

Về bản chất, chỉ mục IVF là một mảng kích thước $k$, mỗi phần tử đại diện cho một centroid và trỏ tới một danh sách động lưu trữ danh sách Vector ID (hoặc Offset bộ nhớ nhị phân) của các điểm dữ liệu nằm trong tế bào Voronoi đó:

Centroid_0 -> [ID_12, ID_99, ID_254, ...]
Centroid_1 -> [ID_3, ID_47, ID_801, ...]
Centroid_2 -> [ID_502, ID_612, ...]

class IVFIndex {
  constructor(centroids, dimension) {
    this.centroids = centroids; // Mảng centroids [k][dimension]
    this.invertedLists = Array.from({ length: centroids.length }, () => []);
  }
  
  // Ghi nhận vector mới vào danh sách đảo ngược
  insert(vectorId, vector) {
    let minDist = Infinity, bestCentroidIdx = 0;
    for (let i = 0; i < this.centroids.length; i++) {
      const dist = vector.reduce((sum, val, d) => sum + Math.pow(val - this.centroids[i][d], 2), 0);
      if (dist < minDist) {
        minDist = dist;
        bestCentroidIdx = i;
      }
    }
    // Chỉ lưu Vector ID vào bucket tương ứng (Tối ưu bộ nhớ)
    this.invertedLists[bestCentroidIdx].push(vectorId);
  }
}

4.4 Quy trình tìm kiếm IVF (Query Pipeline)

Khi có một vector truy vấn $\mathbf{q}$ đầu vào, quy trình tìm kiếm xấp xỉ diễn ra như sau:

1. Tìm Centroid gần nhất: Tính khoảng cách từ vector truy vấn $\mathbf{q}$ đến tất cả $k$ centroids. Lọc ra $n_{\text{probe}}$ centroids gần nhất.
2. Trích xuất Bucket tương ứng: Lấy ra danh sách các Vector ID nằm trong inverted lists của $n_{\text{probe}}$ centroids này.
3. So khớp chi tiết: Lấy tọa độ vector nhị phân của các ID này từ bộ nhớ Hybrid, tính toán khoảng cách thực tế với $\mathbf{q}$, và trả về Top K ứng viên gần nhất.

// Tìm kiếm với nprobe
function searchIVF(query, index, nprobe = 2, limit = 5, database) {
  // 1. Tìm centroids gần query nhất
  const sortedCentroids = index.centroids.map((c, idx) => ({
    idx,
    dist: query.reduce((sum, val, d) => sum + Math.pow(val - c[d], 2), 0)
  })).sort((a, b) => a.dist - b.dist);
  
  // Lấy nprobe centroids hàng đầu
  const activeCentroids = sortedCentroids.slice(0, nprobe);
  const candidates = [];
  
  // 2. Quét tuyến tính chỉ trên các ID thuộc các centroid này
  for (const c of activeCentroids) {
    const ids = index.invertedLists[c.idx];
    for (const id of ids) {
      const vec = database.getVector(id); // Lấy vector thực tế
      const dist = query.reduce((sum, val, d) => sum + Math.pow(val - vec[d], 2), 0);
      candidates.push({ id, distance: Math.sqrt(dist) });
    }
  }
  
  return candidates.sort((a, b) => a.distance - b.distance).slice(0, limit);
}

5.5 Phân tích đánh đổi: Hiện tượng bỏ sót lân cận ở biên Voronoi

Sử dụng chỉ mục IVF giúp tăng tốc độ tìm kiếm hàng chục lần vì ta chỉ quét một phần nhỏ lượng dữ liệu (ví dụ: quét 2 cụm trong số 100 cụm, giảm $98\%$ khối lượng tính toán). Tuy nhiên, đây là tìm kiếm xấp xỉ (approximate) nên có khả năng bỏ sót kết quả chính xác nhất.

Hiện tượng này gọi là Lỗi Biên Voronoi (Voronoi Boundary Problem): Khi điểm dữ liệu nằm rất gần vector truy vấn nhưng lại nằm sát vách ngăn Voronoi sang phía tế bào bên cạnh. Nếu tham số $n_{\text{probe}}$ quá nhỏ, hệ thống sẽ bỏ qua không quét tế bào biên đó và bỏ sót mất điểm tối ưu nhất.

Dưới đây là bảng đối chiếu hiệu năng giữa các giải thuật tìm kiếm:

5.6 Thực hành: Trực quan hóa phân hoạch Voronoi & nprobe

Demo bên dưới sinh ngẫu nhiên khoảng 70 điểm dữ liệu 2D, phân cụm bằng kMeans qua lớp IVFIndex(6, 'euclidean') thật của vdb-engine.js, sau đó gọi build() để đổ dữ liệu vào 6 bucket (danh sách đảo ngược). Kéo thanh trượt nprobe để thay đổi số cụm được quét khi tìm kiếm — các cụm được quét (probed) hiển thị sáng rõ, các cụm bị bỏ qua (skipped) hiển thị mờ xám. Chỉ số scannedPercent hiển thị bên dưới là số thật trả về từ index.search(), không phải số ước lượng.

import { IVFIndex } from './vdb-engine.js';

// Sinh ngau nhien ~70 diem du lieu 2D trong khong gian canvas (co le)
const PADDING = 24;
const dataset = Array.from({ length: 70 }, (_, i) => ({
  id: i,
  vector: [
    PADDING + Math.random() * (640 - 2 * PADDING),
    PADDING + Math.random() * (320 - 2 * PADDING),
  ],
}));

// Xay dung chi muc IVF that: 6 centroids, do do Euclidean
const ivfIndex = new IVFIndex(6, 'euclidean');
dataset.forEach((p) => ivfIndex.insert(p.id, p.vector));
ivfIndex.build(); // chay kMeans that va do du lieu vao 6 buckets

// Moi lan keo slider nprobe -> goi lai search() that, khong mo phong
function onNprobeChange(nprobe) {
  const results = ivfIndex.search(queryPoint, 8, nprobe);
  // results[i].scannedPercent la % du lieu THAT da duoc quet qua
  console.log(`nprobe=${nprobe} -> quet ${results[0].scannedPercent}% du lieu`);
  return results;
}