La ricerca per similarità (in inglese similarity search o vector search) è un'operazione fondamentale nell'ambito dell'informatica e del recupero dell'informazione (information retrieval). A differenza della ricerca puntuale basata su corrispondenze esatte (exact matching), tipica dei database relazionali, la ricerca per similarità si occupa di individuare, all'interno di una collezione di dati, gli elementi che presentano la maggiore affinità o vicinanza concettuale rispetto a un elemento di interrogazione (query).

L'enorme crescita della disponibilità di dati non strutturati (testi, immagini, audio, dati genomici) e la diffusione dei modelli di deep learning hanno reso la ricerca per similarità una componente architetturale essenziale per motori di ricerca moderni, sistemi di raccomandazione e database vettoriali.

Formulazione matematica

In un contesto formale, gli oggetti del dominio vengono rappresentati come vettori all'interno di uno spazio metrico o vettoriale -dimensionale tramite tecniche di embedding. Sia l'insieme di dati di riferimento e il vettore di query.

Funzioni di distanza e similarità

La vicinanza tra gli elementi viene misurata attraverso misure di similarità, funzioni matematiche di distanza o di similarità , quali:

distanza euclidea (norma ):

prodotto scalare:

similarità del coseno:

Tipologie

La ricerca per similarità prevede essenzialmente due varianti:

ricerca k-Nearest Neighbors (k-NN exact search): Trovare l'insieme con tale che per ogni e si abbia . ricerca Nearest Neighbor approssimata (ANN search): Identificare un elemento la cui distanza da sia al massimo volte la distanza reale dal punto più vicino :

Maledizione della dimensionalità

Per spazi a bassa dimensionalità (), strutture dati ad albero come i K-d tree permettono una ricerca esatta con complessità logaritmica . Tuttavia, all'aumentare delle dimensioni , le prestazioni di tali strutture degradano rapidamente fino a equivalere a quelle della scansione lineare esaustiva . Tale fenomeno è noto in letteratura come maledizione della dimensionalità.

Per superare tale limitazione nel caso di vettori ad alta dimensione (spesso o ), la ricerca si è orientata verso algoritmi approssimati che accettano minime perdite di accuratezza (in termini di recall) a fronte di un significativo guadagno in termini di tempo di risposta e memoria utilizzata.

Indicizzazione e algoritmi ANN

Gli algoritmi per la ricerca approssimata per similarità si dividono principalmente in quattro categorie fondamentali:

Indici hash L'indicizzazione Locality-Sensitive Hashing (LSH) utilizza famiglie di funzioni hash progettate in modo che elementi vicini nello spazio metrico abbiano un'elevata probabilità di collidere nello stesso bucket, fornendo garanzie teoriche sul tempo di ricerca richiesto.

Grafi di prossimità Gli indici basati su grafi collegano i vettori in una rete topologica. L'algoritmo HNSW (Hierarchical Navigable Small World) costruisce un grafo gerarchico multi-livello ispirato ai modelli di rete small-world, consentendo una navigazione rapida e scalabile di complessità logaritmica in fase di ricerca.

Quantizzazione e compressione La quantizzazione di prodotto (product quantization) divide lo spazio vettoriale ad alta dimensionalità in sottospazi di piccole dimensioni e quantizza ciascun sottospazio autonomamente. Ciò riduce drasticamente il fabbisogno di memoria e velocizza il calcolo della distanza mediante utilizzo di tabelle di consultazione pre-calcolate.

Inverted File Index (IVF) I metodi basati su partizionamento dello spazio usano tecniche di clustering come il k-means per dividere il dominio in regioni di Voronoi, riducendo lo spazio di ricerca ai soli cluster geograficamente vicini al vettore di query.

Ricerca in spazi metrici

Nel contesto teorico del recupero dell'informazione, è opportuno distinguere il concetto generale di ricerca per similarità da quello specifico di ricerca in spazi metrici ().

Sebbene le due nozioni vengano spesso usate come sinonimi nella pratica, esse operano a livelli di astrazione differenti: Ricerca per similarità: Rappresenta la classe generale dei problemi in cui si cercano elementi "simili" a un'interrogazione. Nella stragrande maggioranza delle applicazioni moderne, si assume che i dati siano espressi come vettori in uno spazio di dimensione fissa, su cui si applicano operazioni algebriche di base (come il prodotto scalare o le norme). Ricerca in spazi metrici: È un paradigma algebrico e di calcolo più astratto. Non richiede dati in forma vettoriale né che sia definita un'algebra vettoriale; l'unica informazione disponibile sugli elementi del dominio è la loro distanza reciproca , a patto che la funzione di distanza soddisfi i quattro assiomi di uno spazio metrico: Non-negatività: Identità degli indiscernibili: Simmetria: Disuguaglianza triangolare:

Proprietà sfruttate dagli algoritmi di indicizzazione La ricerca vettoriale tradizionale sfrutta la geometria dello spazio di dimensionalità fissata (ad es. proiezioni, partizionamento di spazi tramite iperpiani, quantizzazione spaziale). La ricerca metrica si basa esclusivamente sulla disuguaglianza triangolare per potare (eliminare) porzioni del dataset durante l'esplorazione, evitando il calcolo esplicito delle distanze tra la query e tutti gli oggetti del database. Se è nota la distanza tra un punto pivot e un oggetto , e si calcola , la disuguaglianza triangolare permette di stabilire un limite inferiore per senza dover valutare direttamente tale distanza.

Confronto sintetico Si veda .

Caratteristica Ricerca Vettoriale Generale Ricerca in Spazi Metrici Rappresentazione dati Vettori a dimensione fissa Oggetti arbitrari (stringhe, grafi, serie temporali, oggetti complessi) Requisito primario Esistenza di uno spazio di coordinate/embedding Funzione di distanza che soddisfa la disuguaglianza triangolare Operatore fondamentale Algebrico (prodotto interno, norma ) Confronto di distanze scalari relative Tecnica di potatura Iperpiani, cluster Voronoi, grafi topologici Disuguaglianza triangolare tramite pivot (ad es. M-Tree, VP-Tree)

Applicazioni

Database Vettoriali: Motori di ricerca semantica basati su embedding generati da LLM (Large Language Model) e sistemi RAG (Retrieval-Augmented Generation). Computer Vision: Ricerca di immagini simili, riconoscimento facciale e tracciamento di oggetti. Sistemi di Raccomandazione: Filtraggio collaborativo per raccomandare prodotti o contenuti multimediali. Bioinformatica: Confronto e allineamento di sequenze geniche e strutture proteiche.

Note

Categoria:Algoritmi di ricerca Categoria:Spazi vettoriali topologici Categoria:Strutture dati Categoria:Hash Categoria:Geometria metrica