Chỉ Mục Phân Cụm Đảo (Inverted File Index - IVF) Cho Vector Search

Mục tiêu kiến thức

• Hiểu tại sao Flat Index O(N) không thể scale khi kho dữ liệu lên tới 100 triệu vector.
• Kiến trúc Inverted File (IVF):
• Giai đoạn Huấn luyện (Train): Chạy K-Means để chia không gian vector thành C tế bào Voronoi (Voronoi cells), mỗi tế bào có một tâm cụm (centroid).
• Giai đoạn Nạp dữ liệu (Add): Mỗi vector được gán vào tâm cụm gần nhất và lưu trong danh sách liên kết đảo (inverted list) của cụm đó.
• Giai đoạn Truy vấn (Search):
• So khớp vector truy vấn với C tâm cụm, tìm ra nprobe tâm cụm gần nhất (1 ≤ nprobe ≤ C).
• Chỉ duyệt tìm kiếm chi tiết các vector nằm trong nprobe cụm được chọn.
• Giảm số lượng vector cần so khớp từ N xuống ≈ nprobeC N (tăng tốc độ gấp 20x - 100x).

Yêu cầu

Xây dựng lớp IVFFlatIndex:

class IVFFlatIndex:
    def __init__(self, dim: int, nlist: int = 4):
        pass

    def train(self, vectors: np.ndarray, seed: int = 42) -> None:
        pass

    def add(self, vectors: np.ndarray, doc_ids: list[str]) -> None:
        pass

    def search(self, query: np.ndarray, top_k: int = 3, nprobe: int = 1) -> list[tuple[str, float]]:
        pass

• dim: Số chiều vector.
• nlist: Số lượng tâm cụm (centroids).
• nprobe: Số lượng cụm lân cận cần quét khi tìm kiếm.

Ràng buộc

• Thời gian chạy tối đa: 3000ms.
• Giới hạn bộ nhớ: 256MB.
• Dữ liệu đầu vào hợp lệ theo đúng kiểu dữ liệu và miền giá trị được mô tả.