Likhetssökning

Likhetssökning, eller närliggande sökning, är processen att hitta objekt som liknar en given förfrågan i ett visst mått på deras egenskaper. Den är central inom områden som informationsåtervinning, datorseende, ljud- och textanalys samt rekommendationssystem. Vanligtvis representeras data som vektorer i ett rum där varje dimension fångar en egenskap hos objektet. Frågan till systemet lämnas också som en vektor, och målet är att hitta de närmaste grannarna enligt ett avstånds- eller likhetsmått.

Vanliga mått inkluderar cosine similarity, som fokuserar på vektorernas riktning, och olika avståndsmått som L2 (euklidiskt avstånd) eller Manhattan-avstånd. För uppsättningar av material som innehåller set-segment eller binära indikatorer används ofta Jaccardlikhet eller liknande mått. Exakt sökning kan vara mycket kostsam i stora eller högdimensionella datamängder, varför ofta approximativa metoder används.

Indexeringstekniker för effektiv likhetssökning inkluderar strukturer som k-d-träd och ball-träd för lågdimensionell data, samt mer sofistikerade metoder som locality-sensitive hashing (LSH) och produktkvantisering. Modernt används också approximate nearest neighbor-verktyg som HNSW, FAISS, Annoy och ScaNN.

Användningsområden omfattar bild- och videosökning, text- och dokumentlikhet, dubblettidentifiering, och personliga rekommendationer. Viktiga utmaningar är hög dimension, skalbarhet, uppdateringar i realtid och att balansera noggrannhet med svarstid. Vanliga mått för utvärdering inkluderar precision, recall och mean average precision.