Nærmeste-nabo-søgning

Eksakt k-nærmeste-nabo-søgning sammenligner forespørgslen med alle N gemte vektorer, hvilket koster O(N · d) pr. forespørgsel ved dimension d. Det går fint for titusinder af vektorer, især på en GPU, men ikke for hundreder af millioner inden for et latenstidsbudget. Rumopdelende træer som k-d-træer, der virker godt i to eller tre dimensioner, forringes mod brute force ved de flere hundrede dimensioner, som embeddings typisk har, et symptom på dimensionalitetens forbandelse. Metoder til approksimativ nærmeste-nabo-søgning (ANN) accepterer derfor, at nogle rigtige naboer overses, og vurderes efter recall@k (andelen af den eksakte top k, som indekset returnerer) over for forespørgsler pr. sekund, hukommelse og byggetid, som i den offentlige ann-benchmarks-suite.

Tre familier dominerer. Locality-sensitive hashing (Indyk og Motwani, 1998) hasher vektorer, så nærliggende vektorer med høj sandsynlighed kolliderer; metoden har stærke teoretiske garantier, men kræver som regel meget hukommelse for høj recall. Inverted file-indeks (IVF) klynger data med k-means i nlist celler og scanner ved forespørgslen kun de nprobe celler, hvis centroider ligger nærmest; både recall og pris stiger med nprobe. Produktkvantisering (Jégou, Douze og Schmid, 2011) komprimerer hver vektor ved at dele den i m delvektorer og erstatte hver med indekset for en af 256 lærte centroider, så en vektor fylder m bytes, og afstande beregnes ud fra opslagstabeller; IVF-PQ i FAISS-biblioteket (Johnson, Douze og Jégou, 2017) skalerer det til milliarder af vektorer på GPU'er.

Grafindeks er i dag standard i vektordatabaser. HNSW (Malkov og Yashunin, 2018) bygger en proksimitetsgraf i flere lag: Hver knude forbindes med op til M naboer (2M i det nederste lag), de øvre lag er tynde udsnit, der fungerer som motorveje, og søgningen går grådigt nedad fra det øverste lag og holder en kandidatliste af størrelsen efSearch i det nederste lag. Større M og efConstruction forbedrer grafens kvalitet mod mere hukommelse og længere byggetid; efSearch er drejeknappen mellem recall og ventetid pr. forespørgsel. HNSW ligger i hukommelsen og er hurtig, men dyr i RAM, så DiskANN (Subramanya m.fl., 2019), bygget på Vamana-grafen, holder grafen på SSD med komprimerede vektorer i hukommelsen til samlinger i milliardskala.

De fleste driftsproblemer kommer fra filtre og løbende ændringer. Efterfiltrering, hvor indekset søges først og metadata- eller rettighedsbetingelser anvendes bagefter, kan returnere færre end k resultater, når filteret er selektivt: pgvectors dokumentation bemærker, at med standardværdien hnsw.ef_search på 40 og en betingelse, der matcher 10 % af rækkerne, matcher kun omkring fire rækker i gennemsnit, og derfor tilføjede pgvector 0.8.0 (november 2024) iterative indeksscanninger. Forfiltrering kan bryde grafens sammenhæng eller falde tilbage til brute force. Sletninger i grafindeks er som regel tombstones, der forringer recall, indtil indekset komprimeres eller genopbygges, og recall bør overvåges i drift mod en eksakt søgning på et udsnit af forespørgsler frem for at blive antaget ud fra benchmarks.