HNSW_PRQ

HNSW_PRQ sfrutta i grafi Hierarchical Navigable Small World (HNSW) con Product Residual Quantization (PRQ), offrendo un metodo avanzato di indicizzazione vettoriale che consente di regolare con precisione il compromesso tra dimensione dell'indice e accuratezza. PRQ va oltre la tradizionale Quantizzazione del prodotto (PQ) introducendo un passaggio di quantizzazione residua (RQ) per catturare informazioni aggiuntive, ottenendo una maggiore precisione o indici più compatti rispetto ai metodi basati esclusivamente su PQ. Tuttavia, i passaggi aggiuntivi possono comportare un maggiore overhead computazionale durante la costruzione e la ricerca dell'indice.

Panoramica

HNSW_PRQ combina due tecniche di indicizzazione: HSNW per una navigazione veloce basata sui grafi e PRQ per un'efficiente compressione vettoriale.

HNSW

HNSW costruisce un grafo multistrato in cui ogni nodo corrisponde a un vettore del set di dati. In questo grafo, i nodi sono collegati in base alla loro somiglianza, consentendo una rapida navigazione nello spazio dei dati. La struttura gerarchica consente all'algoritmo di ricerca di restringere i vicini candidati, accelerando in modo significativo il processo di ricerca in spazi ad alta dimensionalità.

Per ulteriori informazioni, consultare HNSW.

PRQ

PRQ è un approccio di compressione vettoriale a più stadi che combina due tecniche complementari: PQ e RQ. Suddividendo prima un vettore ad alta dimensione in sottovettori più piccoli (tramite PQ) e quantizzando poi le differenze rimanenti (tramite RQ), PRQ ottiene una rappresentazione compatta ma accurata dei dati originali.

La figura seguente ne illustra il funzionamento.

Hnsw Prq

1. Quantizzazione del prodotto (PQ)

   In questa fase, il vettore originale viene diviso in sottovettori più piccoli e ogni sottovettore viene mappato al centroide più vicino in un codebook appreso. Questa mappatura riduce significativamente le dimensioni dei dati, ma introduce un certo errore di arrotondamento, poiché ogni sottovettore è approssimato da un singolo centroide. Per maggiori dettagli, consultare IVF_PQ.

2. Quantizzazione residua (RQ)

   Dopo la fase PQ, RQ quantizza il residuo - la differenza tra il vettore originale e la sua approssimazione basata su PQ - utilizzando codebook aggiuntivi. Poiché questo residuo è in genere molto più piccolo, può essere codificato in modo più preciso senza un grande aumento di memoria.

   Il parametro nrq determina il numero di volte in cui il residuo viene quantizzato iterativamente, consentendo di regolare con precisione l'equilibrio tra efficienza di compressione e accuratezza.

3. Rappresentazione finale della compressione

   Una volta che RQ ha terminato la quantizzazione del residuo, i codici interi di PQ e RQ vengono combinati in un unico indice compresso. Catturando dettagli raffinati che la sola PQ potrebbe tralasciare, la RQ migliora l'accuratezza senza causare un aumento significativo della memoria. Questa sinergia tra PQ e RQ è ciò che definisce il PRQ.

HNSW + PRQ

Combinando HNSW con PRQ, HNSW_PRQ mantiene la rapida ricerca basata su grafi di HNSW e sfrutta la compressione multistadio di PRQ. Il flusso di lavoro è il seguente:

1. Compressione dei dati: Ogni vettore viene prima trasformato tramite PQ in una rappresentazione grossolana, quindi i residui vengono quantizzati tramite RQ per un ulteriore affinamento. Il risultato è un insieme di codici compatti che rappresentano ciascun vettore.

2. Costruzione del grafico: I vettori compressi (compresi i codici PQ e RQ) costituiscono la base per la costruzione del grafico HNSW. Poiché i dati sono memorizzati in forma compatta, il grafo richiede meno memoria e la navigazione al suo interno è accelerata.

3. Recupero dei candidati: Durante la ricerca, HNSW utilizza le rappresentazioni compresse per attraversare il grafo e recuperare un pool di candidati. Questo riduce drasticamente il numero di vettori da prendere in considerazione.

4. (Opzionale) Affinamento dei risultati: I risultati iniziali dei candidati possono essere raffinati per ottenere una maggiore precisione, in base ai seguenti parametri:

   • refine: Controlla se questa fase di raffinamento è attivata. Se impostato su true, il sistema ricalcola le distanze utilizzando rappresentazioni di maggiore precisione o non compresse.

   • refine_type: Specifica il livello di precisione dei dati utilizzati durante il raffinamento (ad esempio, SQ6, SQ8, BF16). Una scelta di precisione superiore, come FP32, può dare risultati più accurati, ma richiede più memoria. Il livello di precisione deve essere superiore alla precisione dell'insieme di dati compresso originale di sq_type.

   • refine_k: Agisce come fattore di ingrandimento. Ad esempio, se il top k è 100 e refine_k è 2, il sistema classifica nuovamente i 200 candidati migliori e restituisce i 100 migliori, migliorando l'accuratezza complessiva.

Per un elenco completo dei parametri e dei valori validi, consultare la sezione Parametri dell'indice.

Creazione dell'indice

Per costruire un indice HNSW_PRQ su un campo vettoriale in Milvus, utilizzare il metodo add_index(), specificando i parametri index_type, metric_type e altri parametri aggiuntivi per l'indice.

from pymilvus import MilvusClient

# Prepare index building params
index_params = MilvusClient.prepare_index_params()

index_params.add_index(
    field_name="your_vector_field_name", # Name of the vector field to be indexed
    index_type="HNSW_PRQ", # Type of the index to create
    index_name="vector_index", # Name of the index to create
    metric_type="L2", # Metric type used to measure similarity
    params={
        "M": 30, # Maximum number of neighbors each node can connect to in the graph
        "efConstruction": 360, # Number of candidate neighbors considered for connection during index construction
        "m": 384, 
        "nbits": 8,
        "nrq": 1,
        "refine": true, # Whether to enable the refinement step
        "refine_type": "SQ8" # Precision level of data used for refinement
    } # Index building params
)

In questa configurazione:

• index_type: Il tipo di indice da costruire. In questo esempio, impostare il valore su HNSW_PQ.

• metric_type: Il metodo utilizzato per calcolare la distanza tra i vettori. I valori supportati sono COSINE, L2 e IP. Per maggiori dettagli, consultare Tipi di metriche.

• params: Opzioni di configurazione aggiuntive per la costruzione dell'indice. Per i dettagli, fare riferimento a Parametri di costruzione dell'indice.

Una volta configurati i parametri dell'indice, si può creare l'indice usando direttamente il metodo create_index() o passando i parametri dell'indice nel metodo create_collection. Per i dettagli, fare riferimento a Creare una raccolta.

Ricerca nell'indice

Una volta costruito l'indice e inserite le entità, è possibile eseguire ricerche di similarità sull'indice.

search_params = {
    "params": {
        "ef": 10, # Parameter controlling query time/accuracy trade-off
        "refine_k": 1 # The magnification factor
    }
}

res = MilvusClient.search(
    collection_name="your_collection_name", # Collection name
    anns_field="vector_field",  # Vector field name
    data=[[0.1, 0.2, 0.3, 0.4, 0.5]],  # Query vector
    limit=3,  # TopK results to return
    search_params=search_params
)

In questa configurazione:

• params: Opzioni di configurazione aggiuntive per la ricerca sull'indice. Per i dettagli, fare riferimento a Parametri di ricerca specifici per l'indice.

Parametri dell'indice

Questa sezione fornisce una panoramica dei parametri utilizzati per la creazione di un indice e per l'esecuzione di ricerche sull'indice.

Parametri di costruzione dell'indice

La tabella seguente elenca i parametri che possono essere configurati in params durante la creazione di un indice.

	Parametro	Descrizione	Valore Intervallo	Suggerimento per la messa a punto
HNSW	M	Numero massimo di connessioni (o bordi) che ogni nodo può avere nel grafo, compresi i bordi in uscita e in entrata. Questo parametro influisce direttamente sulla costruzione dell'indice e sulla ricerca.	Tipo: Intervallo: [2, 2048] Valore predefinito: 30 (fino a 30 bordi uscenti e 30 bordi entranti per nodo)	Un valore maggiore di M porta generalmente a una maggiore accuratezza, ma aumenta l'overhead di memoria e rallenta sia la costruzione dell'indice che la ricerca. Considerare di aumentare M per i set di dati con elevata dimensionalità o quando è fondamentale un richiamo elevato. Si consiglia di diminuire M quando l'uso della memoria e la velocità di ricerca sono le principali preoccupazioni. Nella maggior parte dei casi, si consiglia di impostare un valore compreso in questo intervallo: [5, 100].
	efConstruction	Numero di vicini candidati considerati per la connessione durante la costruzione dell'indice. Per ogni nuovo elemento viene valutato un pool più ampio di candidati, ma il numero massimo di connessioni effettivamente stabilite è ancora limitato da M.	Tipo: Intervallo: [1, int_max] Valore predefinito: 360	Un valore più alto di efConstruction si traduce tipicamente in un indice più accurato, poiché vengono esplorate più connessioni potenziali. Tuttavia, questo comporta anche tempi di indicizzazione più lunghi e un maggiore utilizzo della memoria durante la costruzione. Considerare l'aumento di efConstruction per migliorare l'accuratezza, soprattutto in scenari in cui il tempo di indicizzazione è meno critico. Considerare di diminuire efConstruction per accelerare la costruzione dell'indice quando le risorse sono limitate. Nella maggior parte dei casi, si consiglia di impostare un valore compreso in questo intervallo: [50, 500].
PRQ	m	Numero di sottovettori (usati per la quantizzazione) in cui dividere ogni vettore ad alta dimensionalità durante il processo di quantizzazione.	Tipo: Intero Intervallo: [1, 65536] Valore predefinito: Nessuno	Un valore più alto di m può migliorare l'accuratezza, ma aumenta anche la complessità computazionale e l'utilizzo di memoria. m deve essere un divisore della dimensione del vettore(D) per garantire una corretta decomposizione. Un valore comunemente consigliato è m = D/2. Nella maggior parte dei casi, si consiglia di impostare un valore compreso in questo intervallo: [D/8, D].
	nbits	Il numero di bit utilizzati per rappresentare l'indice del centroide di ciascun sottovettore nella forma compressa. Determina direttamente la dimensione di ciascun codebook. Ogni codebook conterrà centroidi a 2 bit. Ad esempio, se nbits è impostato su 8, ogni sottovettore sarà rappresentato da un indice del centroide a 8 bit. Ciò consente di avere28 (256) possibili centroidi nel codebook per quel sottovettore.	Tipo: Intervallo di valori: [1, 24] Valore predefinito: 8	Un valore più alto di nbits consente di avere codebook più ampi, che potenzialmente portano a rappresentazioni più accurate dei vettori originali. Tuttavia, significa anche utilizzare più bit per memorizzare ciascun indice, con conseguente minore compressione. Nella maggior parte dei casi, si consiglia di impostare un valore compreso in questo intervallo: [1, 16].
	nrq	Controlla il numero di subquantizzatori residui utilizzati nello stadio RQ. Un numero maggiore di subquantizzatori consente di ottenere una maggiore compressione, ma potrebbe comportare una maggiore perdita di informazioni.	Tipo: Intero Intervallo: [1, 16] Valore predefinito: 2	Un valore più alto di nrq consente ulteriori passaggi di subquantizzazione residua, che potenzialmente portano a una ricostruzione più precisa dei vettori originali. Tuttavia, ciò comporta anche la memorizzazione e il calcolo di un maggior numero di subquantizzatori, con conseguente aumento delle dimensioni dell'indice e un maggiore overhead computazionale.
	refine	Un flag booleano che controlla se viene applicato un passo di raffinamento durante la ricerca. Il raffinamento consiste nel riordinare i risultati iniziali calcolando le distanze esatte tra il vettore di interrogazione e i candidati.	Tipo: Booleano Intervallo: [true, false] Valore predefinito: false	Impostare true se è essenziale un'elevata precisione e si possono tollerare tempi di ricerca leggermente più lenti. Utilizzare false se la velocità è una priorità e un piccolo compromesso nella precisione è accettabile.
	refine_type	Determina la precisione dei dati utilizzati durante il processo di raffinamento. Questa precisione deve essere superiore a quella dei vettori compressi (come impostato dai parametri m e nbits ).	Tipo: String Range:[ SQ6, SQ8, BF16, FP16, FP32 ] Valore predefinito: Nessuno	Utilizzare FP32 per ottenere la massima precisione con un costo di memoria più elevato, oppure SQ6/SQ8 per una migliore compressione. BF16 e FP16 offrono un'alternativa equilibrata.

Parametri di ricerca specifici per l'indice

La tabella seguente elenca i parametri che possono essere configurati in search_params.params per la ricerca sull'indice.

	Parametro	Descrizione	Valore Intervallo	Suggerimento per la messa a punto
HNSW	ef	Controlla l'ampiezza della ricerca durante il recupero dei vicini. Determina il numero di nodi visitati e valutati come potenziali vicini. Questo parametro influisce solo sul processo di ricerca e si applica esclusivamente al livello inferiore del grafo.	Tipo: Intero Intervallo: [1, int_max] Valore predefinito: limit (TopK vicini da restituire)	Un valore maggiore di ef porta generalmente a una maggiore accuratezza della ricerca, poiché vengono considerati più potenziali vicini. Considerare di aumentare ef quando è fondamentale ottenere un richiamo elevato e la velocità di ricerca è meno importante. Considerare di diminuire ef per dare priorità a ricerche più veloci, soprattutto in scenari in cui una leggera riduzione dell'accuratezza è accettabile. Nella maggior parte dei casi, si consiglia di impostare un valore compreso in questo intervallo: [K, 10K].
PRQ	refine_k	Fattore di ingrandimento che controlla quanti candidati in più vengono esaminati durante la fase di raffinamento (reranking), rispetto ai primi K risultati richiesti.	Tipo: Variabile Intervallo: [1, float_max) Valore predefinito: 1	Valori più alti di refine_k possono migliorare il richiamo e l'accuratezza, ma aumentano anche il tempo di ricerca e l'utilizzo delle risorse. Un valore di 1 significa che il processo di raffinamento considera solo i primi K risultati iniziali.