HNSW

Indeks HNSW adalah algoritme pengindeksan berbasis grafik yang dapat meningkatkan performa saat mencari vektor mengambang berdimensi tinggi. Indeks ini menawarkan akurasi pencarian yang sangat baik dan latensi yang rendah, namun membutuhkan overhead memori yang tinggi untuk mempertahankan struktur graf hirarkinya.

Gambaran Umum

Algoritme Hierarchical Navigable Small World (HNSW) membuat grafik berlapis-lapis, seperti peta dengan tingkat pembesaran yang berbeda. Lapisan paling bawah berisi semua titik data, sedangkan lapisan atas terdiri dari subset titik data yang diambil sampelnya dari lapisan bawah.

Dalam hierarki ini, setiap lapisan berisi node yang mewakili titik data, yang dihubungkan oleh tepi yang menunjukkan kedekatannya. Lapisan yang lebih tinggi menyediakan lompatan jarak jauh untuk mendekati target dengan cepat, sedangkan lapisan yang lebih rendah memungkinkan pencarian yang lebih halus untuk mendapatkan hasil yang paling akurat.

Inilah cara kerjanya:

1. Titik masuk: Pencarian dimulai dari titik masuk tetap di lapisan teratas, yang merupakan simpul yang telah ditentukan sebelumnya dalam grafik.
2. Pencarian serakah: Algoritme dengan rakus bergerak ke tetangga terdekat pada lapisan saat ini hingga tidak dapat mendekati vektor kueri. Lapisan atas melayani tujuan navigasi, bertindak sebagai filter kasar untuk menemukan titik masuk potensial untuk pencarian yang lebih baik di tingkat yang lebih rendah.
3. Lapisan turun: Setelah minimum lokal tercapai pada lapisan saat ini, algoritme akan turun ke lapisan yang lebih rendah, menggunakan koneksi yang telah dibuat sebelumnya, dan mengulangi pencarian yang serakah.
4. Penyempurnaanakhir: Proses ini berlanjut hingga lapisan paling bawah tercapai, di mana langkah penyempurnaan akhir mengidentifikasi tetangga terdekat.

HNSW

Kinerja HNSW bergantung pada beberapa parameter kunci yang mengontrol struktur graf dan perilaku pencarian. Parameter-parameter tersebut antara lain:

• M: Jumlah maksimum sisi atau koneksi yang dapat dimiliki oleh setiap simpul dalam graf pada setiap tingkat hirarki. M yang lebih tinggi menghasilkan graf yang lebih padat dan meningkatkan daya ingat dan akurasi karena pencarian memiliki lebih banyak jalur untuk dijelajahi, yang juga menghabiskan lebih banyak memori dan memperlambat waktu penyisipan karena adanya koneksi tambahan. Seperti yang ditunjukkan pada gambar di atas, M = 5 mengindikasikan bahwa setiap simpul pada graf HNSW terhubung langsung dengan maksimal 5 simpul lainnya. Hal ini menciptakan struktur graf yang cukup padat di mana setiap node memiliki banyak jalur untuk mencapai node lainnya.
• efConstruction: Jumlah kandidat yang dipertimbangkan selama konstruksi indeks. efConstruction yang lebih tinggi umumnya menghasilkan kualitas graf yang lebih baik tetapi membutuhkan lebih banyak waktu untuk membangunnya.
• ef: Jumlah tetangga yang dievaluasi selama pencarian. Meningkatkan ef akan meningkatkan kemungkinan menemukan tetangga terdekat tetapi memperlambat proses pencarian.

Untuk detail tentang cara menyesuaikan pengaturan ini agar sesuai dengan kebutuhan Anda, lihat Parameter indeks.

Membangun indeks

Untuk membangun indeks HNSW pada bidang vektor di Milvus, gunakan metode add_index(), tentukan index_type, metric_type, dan parameter tambahan untuk indeks.

from pymilvus import MilvusClient

# Prepare index building params
index_params = MilvusClient.prepare_index_params()

index_params.add_index(
    field_name="your_vector_field_name", # Name of the vector field to be indexed
    index_type="HNSW", # Type of the index to create
    index_name="vector_index", # Name of the index to create
    metric_type="L2", # Metric type used to measure similarity
    params={
        "M": 64, # Maximum number of neighbors each node can connect to in the graph
        "efConstruction": 100 # Number of candidate neighbors considered for connection during index construction
    } # Index building params
)

Dalam konfigurasi ini:

• index_type: Jenis indeks yang akan dibangun. Dalam contoh ini, tetapkan nilainya ke HNSW.

• metric_type: Metode yang digunakan untuk menghitung jarak antara vektor. Nilai yang didukung termasuk COSINE, L2, dan IP. Untuk detailnya, lihat Jenis Metrik.

• params: Opsi konfigurasi tambahan untuk membangun indeks.

  • M: Jumlah maksimum tetangga yang dapat dihubungkan oleh setiap node.
  • efConstruction: Jumlah kandidat tetangga yang dipertimbangkan untuk koneksi selama pembangunan indeks.

  Untuk mempelajari lebih lanjut parameter pembangunan yang tersedia untuk indeks HNSW, lihat Parameter pembangunan indeks.

Setelah parameter indeks dikonfigurasi, Anda dapat membuat indeks dengan menggunakan metode create_index() secara langsung atau mengoper parameter indeks dalam metode create_collection. Untuk detailnya, lihat Membuat Koleksi.

Mencari di indeks

Setelah indeks dibuat dan entitas dimasukkan, Anda dapat melakukan pencarian kemiripan pada indeks.

search_params = {
    "params": {
        "ef": 10, # Number of neighbors to consider during the search
    }
}

res = MilvusClient.search(
    collection_name="your_collection_name", # Collection name
    data=[[0.1, 0.2, 0.3, 0.4, 0.5]],  # Query vector
    limit=10,  # TopK results to return
    search_params=search_params
)

Dalam konfigurasi ini:

• params: Opsi konfigurasi tambahan untuk pencarian pada indeks.

  • ef: Jumlah tetangga yang perlu dipertimbangkan selama pencarian.

  Untuk mempelajari lebih lanjut parameter pencarian yang tersedia untuk indeks HNSW, lihat Parameter pencarian khusus indeks.

Parameter indeks

Bagian ini memberikan ikhtisar parameter yang digunakan untuk membangun indeks dan melakukan pencarian pada indeks.

Parameter pembangunan indeks

Tabel berikut mencantumkan parameter yang dapat dikonfigurasi di params saat membangun indeks.

Parameter pencarian khusus indeks

Tabel berikut mencantumkan parameter yang dapat dikonfigurasi di search_params.params ketika melakukan pencarian di indeks.