[ad_1]
Pencarian tetangga terdekat vektor, yang memberikan hasil yang relevan dengan mencari vektor dengan jarak minimum ke vektor kueri, sangat penting di area pencarian informasi. Banyak algoritma perkiraan pencarian tetangga terdekat (ANNS) telah diusulkan; namun, dalam skenario skala besar, seperti pencarian web, biaya memori menjadi sangat mahal.
Kredit gambar: Pxfuel, lisensi gratis
Sebuah makalah baru-baru ini di arXiv.org berpendapat bahwa pendekatan indeks terbalik sederhana juga dapat mencapai kinerja canggih untuk kumpulan data skala besar dalam hal penarikan kembali, latensi, dan biaya memori.
SPANN, sistem pencarian dan pengindeksan vektor hibrid memori-disk yang sederhana dan efisien, diusulkan. Ini menjamin latensi rendah dan ingatan tinggi dengan sangat mengurangi jumlah akses disk dan meningkatkan kualitas daftar posting. Eksperimen menunjukkan bahwa SPNN lebih dari dua kali lebih cepat daripada algoritme ANNS yang canggih untuk mencapai kualitas ingatan yang sama.
Algoritme dalam memori untuk perkiraan pencarian tetangga terdekat (ANNS) telah mencapai sukses besar untuk pencarian dengan ingatan tinggi yang cepat, tetapi sangat mahal ketika menangani basis data skala sangat besar. Jadi, ada peningkatan permintaan untuk solusi ANNS hybrid dengan memori kecil dan solid-state drive (SSD) yang murah. Dalam makalah ini, kami menyajikan sistem pengindeksan dan pencarian hibrid memori-disk yang sederhana namun efisien, bernama SPNN, yang mengikuti metodologi indeks terbalik. Ini menyimpan titik pusat dari daftar posting di memori dan daftar posting besar di disk. Kami menjamin efisiensi akses disk (latensi rendah) dan penarikan tinggi dengan secara efektif mengurangi nomor akses disk dan mengambil daftar posting berkualitas tinggi. Pada tahap pembuatan indeks, kami mengadopsi algoritma pengelompokan seimbang hierarkis untuk menyeimbangkan panjang daftar posting dan menambah daftar posting dengan menambahkan poin dalam penutupan cluster yang sesuai. Pada tahap pencarian, kami menggunakan skema query-aware untuk secara dinamis memangkas akses daftar posting yang tidak perlu. Hasil percobaan menunjukkan bahwa SPANN adalah 2× lebih cepat dari solusi ANNS mutakhir DiskANN untuk mencapai kualitas penarikan yang sama 90% dengan biaya memori yang sama dalam tiga set data skala miliar. Itu bisa mencapai 90% [email protected] dan [email protected] hanya dalam waktu sekitar satu milidetik dengan biaya memori hanya 32GB. Kode tersedia di ini https URL.
Makalah penelitian: Chen, Q., “SPANN: Pencarian Tetangga Terdekat Berskala Miliar yang Sangat Efisien”, 2021. Tautan: https://arxiv.org/abs/2111.08566
[ad_2]
