Likhetssøk

Likhetssøk er oppgaven med å finne elementer i en samling som ligner på et gitt forespørselselement, basert på en definert likhets- eller avstandsfunksjon mellom datarepresentasjoner. Målet er å returnere de elementene som anses som nærmest forespørselen. Likhetssøk skiller seg fra eksakt matching ved at små variasjoner ofte tillates i dataenes representasjon.

Data kan være ulike typer: numeriske vektorer, binære vektorer, sekvenser eller tekst. Vanlige målefunksjoner inkluderer Euclidisk avstand, kosinuslikhet, Jaccard-indeks, Hamming-avstand og reduserte distanser for spesifikke felt. Valg av måleenhet avhenger av datatype og formålet med søket.

Metoder: ved nøyaktig søk må alle elementer vurderes, noe som kan være kostbart. For storskala bruk benyttes indekser og tilnærmede teknikker for nær-nabo-søk. Eksempler inkluderer k-d-trær, balltre, R-trær, VP-trær, LSH (Locality-Sensitive Hashing) og andre ANN-algoritmer. I tekstsøket brukes ofte vektor- eller omvendte indeksbaserte tilnærminger.

Anvendelser inkluderer bilde- og videoretrieval, dokument- og informasjonsgjenfinning, musikk- og anbefalingssystemer, duplikat- og plagiatkontroll, bio- og genomforskning samt overvåking av lignende mønstre i tidsserier.

Utfordringer og evaluering: høy dimensjonalitet og støy gjør likhetssøk utfordrende, og det innebærer ofte et avveiningsvalg mellom hastighet og nøyaktighet. Evaluering bruker metrikker som presisjon, tilbakekalling, MAP (mean average precision) og MRR (mean reciprocal rank).