PolarDB:Pengambilan\ vektor\ berdimensi\ tinggi\ \(PASE\)

IVFFlat

IVFFlat adalah versi sederhana dari algoritma IVFADC. Algoritma ini mengelompokkan vektor menggunakan k-means, lalu hanya mencari kluster yang paling dekat dengan vektor kueri—melewatkan kluster yang jauh untuk mempercepat pencarian. Presisi meningkat seiring jumlah kluster yang dicari, sehingga Anda dapat menyetelnya secara langsung.

Cara kerja IVFFlat:

1. IVFFlat menerapkan pengelompokan K-means untuk mengelompokkan vektor ke dalam kluster, masing-masing dengan pusat (centroid).

2. Algoritma ini mengidentifikasi n centroid yang paling dekat dengan vektor kueri.

3. Algoritma ini menjelajahi dan mengurutkan semua vektor dalam n kluster tersebut dan mengembalikan k vektor terdekat.

Nilai n yang lebih besar meningkatkan presisi tetapi juga meningkatkan beban komputasi. Berbeda dengan IVFADC yang menggunakan kuantisasi produk pada fase kedua untuk mengurangi biaya traversal (dengan mengorbankan presisi), IVFFlat menggunakan pencarian brute-force—memberi Anda kendali langsung atas pertukaran antara akurasi dan kinerja.

HNSW

HNSW membangun graf hierarkis multi-lapis menggunakan algoritma Navigable Small World (NSW). Setiap lapisan berfungsi sebagai daftar lompat panorama terhadap lapisan di bawahnya, memungkinkan traversal cepat pada set data besar.

Cara kerja HNSW:

1. HNSW membangun struktur dengan beberapa lapisan (graf). Setiap lapisan merupakan panorama dan daftar lompat dari lapisan di bawahnya.

2. Mulai dari elemen acak di lapisan teratas, HNSW mengidentifikasi tetangga dan menambahkannya ke daftar dinamis berukuran tetap yang diurutkan berdasarkan jarak.

3. HNSW terus memperluas tetangga, mengurutkan ulang daftar setelah setiap penambahan, dan hanya menyimpan k elemen teratas. Setelah daftar stabil, HNSW turun ke lapisan berikutnya menggunakan elemen teratas sebagai titik awal.

4. Proses ini diulang hingga pencarian selesai di lapisan paling bawah.

Setelah presisi mencapai tingkat tertentu, Anda tidak dapat meningkatkannya lebih lanjut dengan mengonfigurasi ulang parameter. HNSW juga memerlukan ruang penyimpanan tambahan untuk menyimpan tetangga graf kedekatan.

Konstruksi tipe PASE

Operator <?> menghitung kemiripan antar vektor. Tipe data PASE menerima hingga tiga parameter:

• Parameter 1: Vektor sisi kanan (float4[])

• Parameter 2: Dicadangkan; atur ke 0

• Parameter 3: Metode kemiripan — 0 untuk jarak Euclidean, 1 untuk dot product (inner product)

SELECT ARRAY[2, 1, 1]::float4[] <?> pase(ARRAY[3, 1, 1]::float4[]) AS distance;
SELECT ARRAY[2, 1, 1]::float4[] <?> pase(ARRAY[3, 1, 1]::float4[], 0) AS distance;
SELECT ARRAY[2, 1, 1]::float4[] <?> pase(ARRAY[3, 1, 1]::float4[], 0, 1) AS distance;

Konstruksi berbasis string

Konstruksi berbasis string menggunakan tanda titik dua (:) untuk memisahkan parameter alih-alih argumen fungsi:

SELECT ARRAY[2, 1, 1]::float4[] <?> '3,1,1'::pase AS distance;
SELECT ARRAY[2, 1, 1]::float4[] <?> '3,1,1:0'::pase AS distance;
SELECT ARRAY[2, 1, 1]::float4[] <?> '3,1,1:0:1'::pase AS distance;

Dalam '3,1,1:0:1', segmen pertama adalah vektor, yang kedua adalah parameter cadangan (0), dan yang ketiga adalah metode kemiripan (0 = Euclidean, 1 = dot product).

Persyaratan normalisasi

• Jarak Euclidean: Tidak memerlukan normalisasi.

• Dot product atau cosine: Normalisasi vektor asli terlebih dahulu. Untuk vektor yang dinormalisasi, dot product sama dengan nilai cosine. Misalnya, jika vektor asli adalah , vektor tersebut harus memenuhi: .

Indeks IVFFlat

CREATE INDEX ivfflat_idx ON vectors_table
USING
  pase_ivfflat(vector)
WITH
  (clustering_type = 1, distance_type = 0, dimension = 256, base64_encoded = 0, clustering_params = "10,100");

Parameter

`clustering_params` untuk pengelompokan internal (`clustering_type = 1`)

Format: clustering_sample_ratio,k

• clustering_sample_ratio: Fraksi pengambilan sampel dengan penyebut 1.000. Rentang: (0, 1000]. Contohnya, 1 berarti rasio pengambilan sampel 1/1000. Nilai yang lebih tinggi meningkatkan akurasi tetapi memperlambat pembuatan indeks. Pastikan total catatan yang diambil sampelnya kurang dari 100.000.

• k: Jumlah centroid. Nilai yang lebih tinggi meningkatkan akurasi tetapi memperlambat pembuatan indeks. Rentang yang direkomendasikan adalah [100, 1000].

Indeks HNSW

CREATE INDEX hnsw_idx ON vectors_table
USING
  pase_hnsw(vector)
WITH
  (dim = 256, base_nb_num = 16, ef_build = 40, ef_search = 200, base64_encoded = 0);

Parameter

Kueri dengan indeks IVFFlat

Operator <#> digunakan untuk kueri indeks IVFFlat. Klausul ORDER BY wajib digunakan agar indeks berlaku. Hasil diurutkan secara ascending berdasarkan jarak.

SELECT id, vector <#> '1,1,1'::pase AS distance
FROM vectors_ivfflat
ORDER BY
  vector <#> '1,1,1:10:0'::pase
ASC LIMIT 10;

String kueri '1,1,1:10:0' berisi tiga parameter yang dipisahkan oleh tanda titik dua:

Kueri dengan indeks HNSW

Operator <?> digunakan untuk kueri indeks HNSW. Klausul ORDER BY wajib digunakan agar indeks berlaku. Hasil diurutkan secara ascending berdasarkan jarak.

SELECT id, vector <?> '1,1,1'::pase AS distance
FROM vectors_ivfflat
ORDER BY
  vector <?> '1,1,1:100:0'::pase
ASC LIMIT 10;

String kueri '1,1,1:100:0' berisi tiga parameter yang dipisahkan oleh tanda titik dua:

Hitung dot product (inner product)

Karena dot product vektor yang dinormalisasi sama dengan nilai cosine-nya, fungsi berikut berlaku untuk pencarian dot product maupun cosine similarity. Fungsi ini menggunakan indeks HNSW.

CREATE OR REPLACE FUNCTION inner_product_search(query_vector text, ef integer, k integer, table_name text) RETURNS TABLE (id integer, uid text, distance float4) AS $$
BEGIN
    RETURN QUERY EXECUTE format('
    select a.id, a.vector <?> pase(ARRAY[%s], %s, 1) AS distance from
    (SELECT id, vector FROM %s ORDER BY vector <?> pase(ARRAY[%s], %s, 0) ASC LIMIT %s) a
    ORDER BY distance DESC;', query_vector, ef,  table_name,  query_vector, ef, k);
END
$$
LANGUAGE plpgsql;

Buat indeks IVFFlat dari file centroid eksternal

Ini adalah fitur advanced. Unggah file centroid eksternal ke direktori server yang ditentukan dan referensikan dalam clustering_params. Format file adalah:

Jumlah dimensi|Jumlah centroid|Set data vektor centroid

Contoh:

3|2|1,1,1,2,2,2