🚀 Prova Zilliz Cloud, la versione completamente gestita di Milvus, gratuitamente—sperimenta prestazioni 10 volte più veloci! Prova Ora>>

Inizia

Home BlogsCome iniziare con HNSWlib

Come iniziare con HNSWlib

Engineering

November 25, 2024

Haziqa Sajid

Laricerca semantica consente alle macchine di comprendere il linguaggio e di ottenere risultati di ricerca migliori, il che è essenziale per l'intelligenza artificiale e l'analisi dei dati. Una volta rappresentato il linguaggio sotto forma di embeddings, la ricerca può essere eseguita con metodi esatti o approssimativi. La ricerca approssimativa dei vicini(ANN) è un metodo utilizzato per trovare rapidamente i punti di un set di dati che sono più vicini a un determinato punto di interrogazione, a differenza della ricerca esatta dei vicini, che può essere computazionalmente costosa per i dati ad alta dimensionalità. La RNA consente un reperimento più rapido, fornendo risultati approssimativamente vicini ai vicini più prossimi.

Uno degli algoritmi per la ricerca approssimativa dei vicini (ANN) è HNSW (Hierarchical Navigable Small Worlds), implementato in HNSWlib, che sarà al centro della discussione di oggi. In questo blog, ci occuperemo di:

Comprendere l'algoritmo HNSW.
Esplorare HNSWlib e le sue caratteristiche principali.
Configurazione di HNSWlib, con la costruzione dell'indice e l'implementazione della ricerca.
Confronto con Milvus.

Capire HNSW

Hierarchical Navigable Small Worlds (HNSW) è una struttura di dati a grafo che consente di effettuare ricerche di similarità efficienti, in particolare in spazi ad alta dimensionalità, costruendo un grafo multistrato di reti "small world". Introdotta nel 2016, HNSW risolve i problemi di scalabilità associati ai metodi di ricerca tradizionali, come le ricerche brute-force e ad albero. È ideale per applicazioni che coinvolgono grandi insiemi di dati, come i sistemi di raccomandazione, il riconoscimento delle immagini e la retrieval-augmented generation (RAG).

Perché HNSW è importante

HNSW migliora significativamente le prestazioni della ricerca nearest-neighbor in spazi ad alta densità. La combinazione della struttura gerarchica con la navigabilità small-world evita l'inefficienza computazionale dei metodi precedenti, consentendo di ottenere buone prestazioni anche con insiemi di dati massicci e complessi. Per capirlo meglio, vediamo come funziona ora.

Come funziona HNSW

Strati gerarchici: HNSW organizza i dati in una gerarchia di livelli, dove ogni livello contiene nodi collegati da bordi. I livelli superiori sono più scarsi e consentono di fare ampi "salti" attraverso il grafico, come se si volesse zoomare su una mappa per vedere solo le principali autostrade tra le città. I livelli inferiori aumentano di densità, fornendo dettagli più fini e maggiori connessioni tra i vicini più prossimi.
Concetto di piccoli mondi navigabili: Ogni livello di HNSW si basa sul concetto di rete "small world", in cui i nodi (punti dati) sono a pochi "hop" di distanza l'uno dall'altro. L'algoritmo di ricerca inizia dal livello più alto e scarno e lavora verso il basso, passando a livelli progressivamente più densi per affinare la ricerca. Questo approccio è come passare da una visione globale ai dettagli del livello di vicinato, restringendo gradualmente l'area di ricerca.

Fig. 1: Un esempio di grafico a piccolo mondo navigabile

Struttura simile a un elenco di salti: L'aspetto gerarchico di HNSW assomiglia a una skip list, una struttura di dati probabilistica in cui i livelli più alti hanno meno nodi, consentendo ricerche iniziali più rapide.

Fig. 2: Un esempio di struttura a lista di salto

Per cercare 96 nella lista di salto data, iniziamo dal livello superiore, all'estrema sinistra, con il nodo di intestazione. Spostandoci a destra, incontriamo 31, meno di 96, quindi proseguiamo al nodo successivo. Ora dobbiamo scendere di un livello, dove vediamo di nuovo 31; poiché è ancora inferiore a 96, scendiamo di un altro livello. Trovando ancora una volta 31, ci spostiamo a destra e raggiungiamo 96, il nostro valore target. In questo modo, troviamo 96 senza dover scendere ai livelli più bassi dell'elenco di salto.

Efficienza della ricerca: L'algoritmo HNSW parte da un nodo di ingresso al livello più alto, procedendo verso i vicini più vicini a ogni passo. Scende attraverso i livelli, utilizzando ciascuno di essi per l'esplorazione da grossolana a fine, fino a raggiungere il livello più basso, dove è probabile che si trovino i nodi più simili. Questa navigazione a strati riduce il numero di nodi e bordi da esplorare, rendendo la ricerca veloce e accurata.
Inserimento e manutenzione: Quando si aggiunge un nuovo nodo, l'algoritmo determina il suo livello di ingresso in base alla probabilità e lo connette ai nodi vicini utilizzando un'euristica di selezione dei vicini. L'euristica mira a ottimizzare la connettività, creando collegamenti che migliorano la navigabilità, bilanciando la densità del grafo. Questo approccio mantiene la struttura robusta e adattabile a nuovi dati.

Pur avendo una conoscenza di base dell'algoritmo HNSW, la sua implementazione da zero può risultare complessa. Fortunatamente, la comunità ha sviluppato librerie come HNSWlib per semplificarne l'uso, rendendolo accessibile senza doversi grattare la testa. Diamo quindi un'occhiata più da vicino a HNSWlib.

Panoramica di HNSWlib

HNSWlib, una popolare libreria che implementa HNSW, è altamente efficiente e scalabile, con buone prestazioni anche con milioni di punti. Raggiunge una complessità temporale sublineare consentendo salti rapidi tra i livelli del grafo e ottimizzando la ricerca di dati densi e ad alta dimensionalità. Ecco le caratteristiche principali di HNSWlib:

Struttura a grafo: Un grafo a più livelli rappresenta i punti di dati, consentendo ricerche rapide e vicine.
Efficienza ad alta dimensione: Ottimizzato per i dati ad alta dimensionalità, fornisce ricerche approssimative rapide e accurate.
Tempo di ricerca sublineare: raggiunge una complessità sublineare saltando gli strati, migliorando notevolmente la velocità.
Aggiornamenti dinamici: Supporta l'inserimento e l'eliminazione di nodi in tempo reale senza richiedere la ricostruzione completa del grafo.
Efficienza della memoria: Utilizzo efficiente della memoria, adatto a grandi insiemi di dati.
Scalabilità: Si adatta bene a milioni di punti di dati, il che lo rende ideale per applicazioni su media scala come i sistemi di raccomandazione.

Nota: HNSWlib è eccellente per creare semplici prototipi di applicazioni di ricerca vettoriale. Tuttavia, a causa dei limiti di scalabilità, potrebbero esserci scelte migliori, come database vettoriali appositamente creati per scenari più complessi che coinvolgono centinaia di milioni o addirittura miliardi di punti di dati. Vediamolo in azione.

Iniziare con HNSWlib: Guida passo-passo

Questa sezione illustra l'uso di HNSWlib come libreria di ricerca vettoriale, creando un indice HNSW, inserendo dati ed eseguendo ricerche. Iniziamo con l'installazione:

Installazione e importazioni

Per iniziare a usare HNSWlib in Python, occorre innanzitutto installarla con pip:

pip install hnswlib

Quindi, importare le librerie necessarie:

import hnswlib 
import numpy as np

Preparazione dei dati

In questo esempio, utilizzeremo NumPyper generare un set di dati casuali con 10.000 elementi, ciascuno con dimensione 256.

dim = 256  # Dimensionality of your vectors
num_elements = 10000  # Number of elements to insert

Creiamo i dati:

data = np.random.rand(num_elements, dim).astype(np.float32)  # Example data

Ora che i dati sono pronti, costruiamo un indice.

Costruire un indice

Per costruire un indice, dobbiamo definire la dimensione dei vettori e il tipo di spazio. Creiamo un indice:

p = hnswlib.Index(space='l2', dim=dim)

space='l2': Questo parametro definisce la metrica di distanza utilizzata per la similarità. Impostarlo su 'l2' significa utilizzare la distanza euclidea (norma L2). Se invece si imposta 'ip', si utilizzerà il prodotto interno, utile per operazioni come la somiglianza del coseno.

dim=dim: Questo parametro specifica la dimensionalità dei punti dati con cui si lavorerà. Deve corrispondere alla dimensione dei dati che si intende aggiungere all'indice.

Ecco come inizializzare un indice:

p.init_index(max_elements=num_elements, ef_construction=200, M=16)

max_elements=num_elements: Imposta il numero massimo di elementi che possono essere aggiunti all'indice. Num_elements è la capacità massima, quindi lo impostiamo a 10.000 poiché stiamo lavorando con 10.000 punti dati.

ef_construction=200: Questo parametro controlla il compromesso tra precisione e velocità di costruzione durante la creazione dell'indice. Un valore più alto migliora il richiamo (precisione) ma aumenta l'utilizzo della memoria e il tempo di costruzione. I valori comuni vanno da 100 a 200.

M=16: Questo parametro determina il numero di collegamenti bidirezionali creati per ogni punto dati, influenzando la precisione e la velocità di ricerca. I valori tipici sono compresi tra 12 e 48; 16 è spesso un buon equilibrio tra precisione e velocità.

p.set_ef(50)  # This parameter controls the speed/accuracy trade-off

ef: Il parametro ef, abbreviazione di "fattore di esplorazione", determina il numero di vicini esaminati durante la ricerca. Un valore più alto di ef comporta l'esplorazione di un maggior numero di vicini, il che generalmente aumenta l'accuratezza (recall) della ricerca, ma la rende anche più lenta. Al contrario, un valore di ef più basso può rendere la ricerca più veloce, ma potrebbe ridurre l'accuratezza.

In questo caso, l'impostazione di ef a 50 significa che l'algoritmo di ricerca valuterà fino a 50 vicini per trovare i punti dati più simili.

Nota: ef_construction imposta lo sforzo di ricerca dei vicini durante la creazione dell'indice, migliorando l'accuratezza ma rallentando la costruzione. ef controlla lo sforzo di ricerca durante l'interrogazione, bilanciando velocità e richiamo in modo dinamico per ogni interrogazione.

Esecuzione delle ricerche

Per eseguire una ricerca di nearest neighbor con HNSWlib, si crea innanzitutto un vettore di query casuale. In questo esempio, la dimensionalità del vettore corrisponde ai dati indicizzati.

query_vector = np.random.rand(dim).astype(np.float32)  # Example query

labels, distances = p.knn_query(query_vector, k=5)  # k is the number of nearest neighbors

query_vector: Questa riga genera un vettore casuale con la stessa dimensionalità dei dati indicizzati, garantendo la compatibilità con la ricerca nearest neighbor.
knn_query: Il metodo cerca i k vicini più prossimi di query_vector all'interno dell'indice p. Restituisce due array: labels, che contengono gli indici dei vicini più prossimi, e distances, che indicano le distanze del vettore di interrogazione da ciascuno di questi vicini. In questo caso, k=5 specifica che vogliamo trovare i cinque vicini più prossimi.

Ecco i risultati dopo la stampa delle etichette e delle distanze:

print("Nearest neighbors' labels:", labels)
print("Distances:", distances)

> Nearest neighbors' labels: [[4498 1751 5647 4483 2471]]
> Distances: [[33.718    35.484592 35.627766 35.828312 35.91495 ]]

Ecco una semplice guida per iniziare a lavorare con HNSWlib.

Come già detto, HNSWlib è un ottimo motore di ricerca vettoriale per la prototipazione o la sperimentazione con insiemi di dati di medie dimensioni. Se avete requisiti di scalabilità più elevati o necessitate di altre funzionalità di livello aziendale, potreste dover scegliere un database vettoriale appositamente creato, come Milvus open-source o il suo servizio completamente gestito su Zilliz Cloud. Nella sezione seguente, quindi, confronteremo HNSWlib con Milvus.

HNSWlib e i database vettoriali come Milvus

Un database vettoriale memorizza i dati come rappresentazioni matematiche, consentendo ai modelli di apprendimento automatico di alimentare la ricerca, le raccomandazioni e la generazione di testi, identificando i dati attraverso metriche di somiglianza per la comprensione del contesto.

Le librerie di indici vettoriali come HNSWlib migliorano laricerca e il recupero dei vettori, ma non hanno le caratteristiche di gestione di un database completo. D'altra parte, i database vettoriali, come Milvus, sono progettati per gestire le incorporazioni vettoriali su scala, offrendo vantaggi nella gestione dei dati, nell'indicizzazione e nelle capacità di interrogazione che le librerie autonome di solito non hanno. Ecco alcuni altri vantaggi dell'uso di Milvus:

Ricerca di similarità vettoriale ad alta velocità: Milvus offre prestazioni di ricerca a livello di millisecondi su insiemi di dati vettoriali su scala miliardaria, ideali per applicazioni come il recupero di immagini, i sistemi di raccomandazione, l'elaborazione del linguaggio naturale(NLP) e la generazione aumentata del recupero (RAG).
Scalabilità e alta disponibilità: Costruito per gestire volumi di dati enormi, Milvus è scalabile orizzontalmente e include meccanismi di replica e failover per garantire l'affidabilità.
Architettura distribuita: Milvus utilizza un'architettura distribuita e scalabile che separa l'archiviazione e l'elaborazione su più nodi per garantire flessibilità e robustezza.
Ricerca ibrida: Milvus supporta la ricerca multimodale, la ricerca ibrida rada e densa e la ricerca ibrida densa e full-text, offrendo funzionalità di ricerca versatili e flessibili.
Supporto flessibile dei dati: Milvus supporta diversi tipi di dati, vettori, scalari e strutturati, consentendo una gestione e un'analisi senza soluzione di continuità in un unico sistema.
Comunità e supportoattivi: Una fiorente comunità fornisce aggiornamenti, tutorial e supporto regolari, assicurando che Milvus rimanga allineato alle esigenze degli utenti e ai progressi del settore.
Integrazione dell'intelligenza artificiale: Milvus si è integrato con diversi framework e tecnologie di IA popolari, rendendo più facile per gli sviluppatori costruire applicazioni con i loro stack tecnologici familiari.

Milvus offre anche un servizio completamente gestito su Ziliz Cloud, che è privo di problemi e 10 volte più veloce di Milvus.

Confronto: Milvus vs. HNSWlib

Caratteristiche	Milvus	HNSWlib
Scalabilità	Gestisce miliardi di vettori con facilità	Adatto a set di dati più piccoli grazie all'utilizzo della RAM
Ideale per	Prototipi, esperimenti e applicazioni di livello aziendale	Si concentra sui prototipi e sulle attività ANN leggere
Indicizzazione	Supporta oltre 10 algoritmi di indicizzazione, tra cui HNSW, DiskANN, Quantization e Binary.	Utilizza solo HNSW basato su grafo
Integrazione	Offre API e servizi cloud-nativi	Funge da libreria leggera e indipendente
Prestazioni	Ottimizza le query distribuite e su grandi dati	Offre alta velocità ma scalabilità limitata

Nel complesso, Milvus è generalmente preferibile per le applicazioni di produzione su larga scala con esigenze di indicizzazione complesse, mentre HNSWlib è ideale per la prototipazione e i casi d'uso più semplici.

Conclusione

La ricerca semantica può richiedere molte risorse, quindi la strutturazione interna dei dati, come quella eseguita da HNSW, è essenziale per un recupero più rapido dei dati. Librerie come HNSWlib si preoccupano dell'implementazione, in modo che gli sviluppatori abbiano le ricette pronte per prototipare le funzionalità del vettore. Con poche righe di codice, possiamo costruire il nostro indice ed eseguire ricerche.

HNSWlib è un ottimo modo per iniziare. Tuttavia, se si desidera creare applicazioni di intelligenza artificiale complesse e pronte per la produzione, i database vettoriali appositamente creati sono l'opzione migliore. Per esempio, Milvus è un database vettoriale open-source con molte caratteristiche enterprise-ready, come la ricerca vettoriale ad alta velocità, la scalabilità, la disponibilità e la flessibilità in termini di tipi di dati e linguaggio di programmazione.