Keluarga Indeks

Struktur yang digunakan indeks ANN untuk mempercepat pencarian dapat disusun dengan tiga cara yang berbeda. Topik ini memetakan keluarga IVF yang mengelompokkan vektor ke dalam klaster, keluarga HNSW yang menavigasi graf berlapis, dan kuantisasi yang mengompresi vektor, lalu menyimulasikan IVF pada 600 titik agar perilakunya terlihat pada angka yang benar-benar dihitung.

Tiga keluarga indeks ANN#

Ketiga keluarga tidak saling meniadakan, melainkan berbeda dalam jenis informasi yang disimpan. IVF menyimpan pembagian klaster, HNSW menyimpan tautan antartitik pada graf, dan kuantisasi menyimpan versi ringkas dari vektor itu sendiri. Tabel berikut merangkum mekanisme dan parameter utamanya.

Parameter yang berlaku saat membangun menentukan bentuk indeks dan hanya dapat diubah dengan membangun ulang, sedangkan parameter saat mencari dapat dinaikkan atau diturunkan per sesi. Kuantisasi menempati posisi khusus karena kompresinya tidak mengubah arah pencarian, sehingga biasanya digunakan bersama IVF atau HNSW, bukan menggantikannya. Bagian berikut membahas ketiganya satu per satu, dengan IVF disimulasikan lebih dahulu karena perhitungannya paling mudah ditelusuri.

IVF: hanya klaster terdekat yang dipindai#

IVF, singkatan dari inverted file, membagi seluruh vektor ke dalam sejumlah klaster dengan algoritma pengelompokan seperti k-means. Setiap klaster memiliki satu centroid, yaitu titik tengah yang mewakili anggota-anggotanya. Saat pembangunan, setiap vektor dicatat ke daftar klaster tempat ia tergabung. Saat pencarian, jarak query ke setiap centroid dihitung, klaster dengan $n_{\text{probe}}$ centroid terdekat dipilih, lalu vektor di dalam klaster terpilih itu saja yang dipindai.

Efek hematnya langsung terlihat pada jumlah jarak yang dihitung. Pemindaian eksak menghitung $O(n)$ jarak per query, sedangkan IVF memindai kira-kira $n \cdot n_{\text{probe}} / \text{lists}$ vektor, yakni proporsi klaster yang dipilih terhadap seluruh klaster. Biaya pembandingan dengan centroid hanya berjumlah $\text{lists}$ jarak per query dan sering diabaikan pada perhitungan kasar. Diagram berikut menunjukkan query yang menyapu dua klaster terdekatnya dan melewati sisanya.

Pada diagram, query memilih klaster A dan B karena centroidnya paling dekat, sehingga seluruh titik pada kedua klaster itu dipindai. Titik pada klaster C tidak pernah dibandingkan dengan query, sekecil apa pun jaraknya sebenarnya. Sifat aproksimatif IVF muncul pada titik ini: apabila salah satu tetangga terbaik ternyata berada di klaster yang dilewati, tetangga itu hilang dari hasil, sebagaimana angka simulasi berikutnya menunjukkan.

Pada pgvector, jumlah klaster diatur dengan lists saat indeks dibuat, sedangkan jumlah klaster yang disapu diatur per sesi dengan ivfflat.probes:

-- tidak-dijalankan
CREATE INDEX ON items USING ivfflat (embedding vector_cosine_ops)
    WITH (lists = 100);

Nilai lists = 100 pada contoh berarti seluruh data dibagi ke dalam 100 klaster. Dengan pembagian yang seimbang, setiap klaster memuat kira-kira satu persen vektor, sehingga ivfflat.probes = 1 hanya menyapu sekitar satu persen data per query dan menaikkan probes berarti menaikkan proporsi itu.

Simulasi IVF pada 600 titik#

Simulasi berikut meniru IVF pada skala kecil agar setiap angka dapat ditelusuri. Datasetnya 600 titik yang berasal dari tiga kelompok berjauhan, sehingga pembagian k-means menghasilkan tiga klaster yang mengikuti kelompok aslinya. Query sengaja ditempatkan di perbatasan dua kelompok, lalu pencarian dijalankan dua kali dengan $n_{\text{probe}} = 1$ dan $n_{\text{probe}} = 2$. Jawaban eksak dari pemindaian penuh digunakan sebagai pembanding untuk menghitung recall@10.

"""Simulasi IVF kecil: query hanya memindai klaster yang centroid-nya terdekat."""
import numpy as np
from sklearn.cluster import KMeans

rng = np.random.default_rng(21)

# Tiga kelompok data yang berjauhan, dijadikan satu dataset 600 titik
kelompok_a = rng.standard_normal((220, 2))
kelompok_b = rng.standard_normal((220, 2)) + [9.0, 0.0]
kelompok_c = rng.standard_normal((160, 2)) + [4.0, 8.0]
X = np.vstack([kelompok_a, kelompok_b, kelompok_c])

# Tahap pembangunan: seluruh titik dibagi ke dalam tiga klaster
kmeans = KMeans(n_clusters=3, n_init=10, random_state=42).fit(X)
label = kmeans.labels_
centroid = kmeans.cluster_centers_

for c in range(3):
    print(f"ukuran klaster {c}: {int((label == c).sum())} titik")

# Query sengaja diletakkan di perbatasan antara dua kelompok data
q = np.array([4.5, 0.3])
k = 10

# Jawaban eksak untuk pembanding: seluruh 600 titik dipindai
jarak_penuh = np.linalg.norm(X - q, axis=1)
eksak = set(map(int, np.argsort(jarak_penuh)[:k]))

for nprobe in (1, 2):
    # Tahap pencarian: pilih nprobe klaster dengan centroid terdekat dari query
    jarak_centroid = np.linalg.norm(centroid - q, axis=1)
    terpilih = np.argsort(jarak_centroid)[:nprobe]
    kandidat = np.flatnonzero(np.isin(label, terpilih))
    jarak_kandidat = np.linalg.norm(X[kandidat] - q, axis=1)
    hasil = kandidat[np.argsort(jarak_kandidat)[:k]]
    irisan = len(set(map(int, hasil)) & eksak)
    print(f"nprobe = {nprobe}: klaster {sorted(map(int, terpilih))} dipindai")
    print(f"  titik dipindai = {kandidat.size} dari {X.shape[0]}, recall@{k} = {irisan / k:.2f}")

ukuran klaster 0: 220 titik
ukuran klaster 1: 160 titik
ukuran klaster 2: 220 titik
nprobe = 1: klaster [2] dipindai
  titik dipindai = 220 dari 600, recall@10 = 0.50
nprobe = 2: klaster [0, 2] dipindai
  titik dipindai = 440 dari 600, recall@10 = 1.00

Keluaran menunjukkan dua hal sekaligus. Dengan $n_{\text{probe}} = 1$, hanya 220 dari 600 titik yang dipindai, sekitar 37 persen, tetapi separuh tetangga terbaiknya hilang sehingga recall@10 hanya 0,50. Dengan $n_{\text{probe}} = 2$, jumlah titik yang dipindai naik menjadi 440, sekitar 73 persen, dan recall@10 kembali ke 1,00 karena kedua klaster yang memuat tetangga terbaik ikut disapu. Query di perbatasan memang memaksimalkan risiko ini, tetapi kasus serupa banyak terjadi pada data nyata karena query jarang jatuh tepat di tengah sebuah klaster.

Angka biaya pada simulasi dinyatakan sebagai jumlah titik yang dipindai, bukan waktu. Jumlah titik bersifat deterministik dan berlaku sama di mesin mana pun, sedangkan waktu bergantung pada perangkat kerasnya. Hubungan keduanya kualitatif: memindai 440 titik memerlukan perhitungan jarak lebih banyak daripada 220 titik, sehingga pengaturan yang lebih longgar selalu menaikkan beban perhitungan per query.

HNSW: navigasi pada graf berlapis#

HNSW, singkatan dari Hierarchical Navigable Small World, adalah keluarga indeks yang menata vektor sebagai graf tetangga dengan beberapa lapisan. Lapisan teratas berisi sedikit titik dengan tautan jarak jauh yang berfungsi sebagai jalan pintas, sedangkan lapisan bawah berisi lebih banyak titik dengan tautan yang lebih rapat. Pencarian dimulai dari lapisan atas dengan langkah serakah menuju titik yang makin dekat ke query, kemudian turun lapis demi lapis hingga mencapai lapisan data.

Kualitas dan biaya pencariannya diatur oleh tiga parameter. Parameter m menentukan jumlah tautan per titik dan umumnya bernilai 16, ef_construction mengatur ukuran kumpulan kandidat saat graf dibangun dengan nilai umum 64, dan ef_search memperluas kumpulan kandidat saat pencarian berlangsung. Nilai ef_search yang lebih besar membuat pencarian menelusuri lebih banyak kandidat, sehingga recall naik seiring biaya per query bertambah, dengan pola yang sama seperti nprobe pada IVF. Perintah berikut membuat indeks HNSW pada pgvector dengan nilai-nilai umum tersebut:

-- tidak-dijalankan
CREATE INDEX ON items USING hnsw (embedding vector_cosine_ops)
    WITH (m = 16, ef_construction = 64);

Perbandingan singkat dengan IVF: IVF murah saat dibangun dan biayanya mudah diprediksi melalui jumlah klaster yang disapu, sedangkan HNSW biasanya memberi recall lebih tinggi pada kecepatan yang sama, dengan biaya memori yang lebih besar untuk tautan grafnya.

Kuantisasi: kompresi sebelum jarak dihitung#

Kuantisasi, atau quantization, menyimpan vektor dalam bentuk yang lebih kecil daripada bilangan pecahan penuh. Kuantisasi skalar 8-bit menyimpan setiap komponen sebagai satu byte, product quantization memecah vektor menjadi beberapa segmen dan mewakilinya dengan kode pendek, sedangkan kuantisasi biner menyimpan setiap komponen sebagai satu bit. Memori yang turun berlipat membuat lebih banyak vektor muat di memori, dan perhitungan jarak menjadi lebih murah karena beroperasi pada data yang lebih pendek.

Harga yang dibayar adalah ketelitian jarak. Jarak yang dihitung dari vektor terkompresi merupakan perkiraan, sehingga peringkat hasil dapat bergeser dan beberapa tetangga terbaik dapat terlewat. Padanan pada pgvector tersedia dalam bentuk tipe halfvec yang menyimpan komponen sebagai bilangan pecahan 16-bit dan tipe bit untuk penyimpanan biner, sedangkan Qdrant menyediakan opsi kuantisasi yang diaktifkan pada koleksinya. Karena kompresi tidak mengubah arah pencarian, kuantisasi sering dikombinasikan dengan IVF atau HNSW sehingga pemindaiannya bekerja pada representasi ringkas di atas struktur klaster atau graf yang sama.

Ringkasan#

• IVF membagi vektor ke dalam klaster dan memindai hanya $n_{\text{probe}}$ klaster dengan centroid terdekat, sehingga biayanya kira-kira $n \cdot n_{\text{probe}} / \text{lists}$ per query.
• HNSW menata vektor sebagai graf berlapis dan mengatur pencariannya dengan m, ef_construction, dan ef_search.
• Kuantisasi mengompresi vektor untuk menurunkan memori dan biaya jarak, dengan risiko peringkat bergeser, dan dapat dikombinasikan dengan IVF atau HNSW.

Referensi#

• Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs — arXiv — Artikel asli Malkov dan Yashunin yang memperkenalkan struktur graf berlapis HNSW.
• pgvector — GitHub — Dokumentasi pgvector yang mencakup indeks HNSW dan IVFFlat serta tipe halfvec dan bit.
• Qdrant Documentation — Qdrant — Dokumentasi Qdrant yang mencakup opsi indeks dan kuantisasi pada mesin vektor.