HNSW_SQ

HNSW_SQ combina i grafi Hierarchical Navigable Small World (HNSW) con la Quantizzazione Scalare (SQ), creando un metodo di indicizzazione vettoriale avanzato che offre un compromesso controllabile tra dimensione e precisione. Rispetto ai grafi HNSW standard, questo tipo di indice mantiene un'elevata velocità di elaborazione delle query, pur introducendo un leggero aumento del tempo di costruzione dell'indice.

Panoramica

HNSW_SQ combina due tecniche di indicizzazione: HNSW per una navigazione veloce basata sui grafi e SQ 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.

SQ

SQ è un metodo per comprimere i vettori rappresentandoli con un minor numero di bit. Ad esempio:

• SQ8 utilizza 8 bit, mappando i valori in 256 livelli. Per ulteriori informazioni, consultare FIV_SQ8.

• SQ6 utilizza 6 bit per rappresentare ciascun valore in virgola mobile, ottenendo 64 livelli discreti.

Hnsw Sq

Questa riduzione della precisione riduce drasticamente l'ingombro in memoria e velocizza il calcolo, pur mantenendo la struttura essenziale dei dati.

SQ4UCompatible with Milvus 2.6.8+

Per gli scenari che richiedono un'estrema velocità di interrogazione e un utilizzo minimo della memoria, Milvus introduce SQ4U, una quantizzazione scalare uniforme a 4 bit. Si tratta di una forma aggressiva di quantizzazione scalare che comprime il valore in virgola mobile di ogni dimensione in un intero senza segno a 4 bit.

La "U" di SQ4U sta per Uniform. A differenza della Quantizzazione scalare non uniforme, che in genere calcola i valori minimi e massimi in modo indipendente per ogni dimensione (Quantizzazione per dimensione), SQ4U applica una strategia di Quantizzazione uniforme globale:

1. Statistica globale: Il sistema calcola un unico valore minimo vmin e un unico intervallo di valori vdiff che si applica a tutte le dimensioni del vettore (o all'intero segmento vettoriale).

2. Mappatura uniforme: L'intervallo di valori globale è suddiviso in 16 intervalli uguali. Ogni valore in virgola mobile del vettore, indipendentemente dalla dimensione a cui appartiene, viene mappato su un intero a 4 bit (0-15) utilizzando questi parametri condivisi.

Vantaggi in termini di prestazioni:

• Rapporto di compressione 8x: Riduce le dimensioni di 8 volte rispetto a FP32 e di 2 volte rispetto a SQ8, riducendo in modo significativo la pressione sulla larghezza di banda della memoria, spesso il collo di bottiglia della ricerca vettoriale.

• Ottimizzazione SIMD: La struttura compatta consente alle moderne CPU (AVX2/AVX-512) di elaborare più dimensioni per ciclo. Inoltre, l'uso di parametri globali elimina la necessità di caricare valori di scala/offset variabili durante il calcolo della distanza, mantenendo la pipeline delle istruzioni completamente satura.

• Efficienza della cache: Le dimensioni ridotte dei vettori consentono di inserire più dati nella cache della CPU, riducendo la latenza causata dall'accesso alla memoria.

HNSW + SQ

HNSW_SQ combina i punti di forza di HNSW e SQ per consentire un'efficiente ricerca approssimativa dei vicini. Ecco come funziona il processo:

1. Compressione dei dati: SQ comprime i vettori utilizzando sq_type (ad esempio, SQ6 o SQ8), riducendo così l'utilizzo della memoria. Questa compressione può ridurre la precisione, ma permette al sistema di gestire insiemi di dati più grandi.

2. Costruzione del grafico: I vettori compressi vengono utilizzati per costruire un grafico HNSW. Poiché i dati sono compressi, il grafo risultante è più piccolo e più veloce da cercare.

3. Recupero dei candidati: Quando viene fornito un vettore di interrogazione, l'algoritmo utilizza i dati compressi per identificare rapidamente un gruppo di vicini candidati dal grafo HNSW.

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 affinamento è 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_SQ 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_SQ", # 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": 64, # Maximum number of neighbors each node can connect to in the graph
        "efConstruction": 100, # Number of candidate neighbors considered for connection during index construction
        "sq_type": "SQ6", # Scalar quantizer type
        "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_SQ.

• 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: Intero Intervallo: [2, 2048] Valore predefinito: 30 (fino a 30 bordi uscenti e 30 bordi entranti per nodo)	Un M più grande porta generalmente a una maggiore accuratezza, ma aumenta l'overhead di memoria e rallenta la costruzione dell'indice e la ricerca. Considerare l'aumento di M per i set di dati con elevata dimensionalità o quando è fondamentale un richiamo elevato. Considerare 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: Intero Intervallo: [1, int_max] Valore predefinito: 360	Un valore più alto di efConstruction produce in genere un indice più accurato, poiché vengono esplorate più connessioni potenziali. Tuttavia, ciò comporta anche tempi di indicizzazione più lunghi e un maggiore utilizzo della memoria durante la costruzione. Considerare di aumentare 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].
SQ	sq_type	Specifica il metodo di quantizzazione scalare per la compressione dei vettori. Ogni opzione offre un diverso equilibrio tra compressione e precisione: SQ4U: Codifica i vettori utilizzando una quantizzazione uniforme a 4 bit. Questa modalità offre la massima velocità e compressione. SQ6: Codifica i vettori utilizzando numeri interi a 6 bit. SQ8: Codifica vettori utilizzando numeri interi a 8 bit. BF16: Utilizza il formato Bfloat16. FP16: Utilizza il formato standard a virgola mobile a 16 bit.	Tipo: Stringa Intervallo: [ SQ4U, SQ6, SQ8, BF16, FP16 ] Valore predefinito: SQ8	La scelta di sq_type dipende dalle esigenze specifiche dell'applicazione. SQ4U è scelto per la massima velocità ed efficienza della memoria. SQ6 o SQ8 potrebbero essere adatti per prestazioni equilibrate. D'altra parte, se l'accuratezza è fondamentale, si potrebbero preferire BF16 o FP16.
	refine	Un flag booleano che controlla se viene applicato un passo di raffinamento durante la ricerca. L'affinamento consiste nel riordinare i risultati iniziali calcolando le distanze esatte tra il vettore della query 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 per il raffinamento. Questa precisione deve essere superiore a quella dei vettori compressi (impostata da sq_type), influenzando sia l'accuratezza dei vettori riordinati che il loro ingombro in memoria.	Tipo: Stringa Intervallo:[ 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 nearest neighbors da restituire)	Un valore maggiore di ef porta generalmente a una maggiore accuratezza della ricerca, poiché vengono considerati più potenziali vicini. Tuttavia, questo aumenta anche il tempo di ricerca. 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].
SQ	refine_k	Fattore di ingrandimento che controlla quanti candidati in più vengono esaminati durante la fase di raffinamento, 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.