HNSW_PRQ

HNSW_PRQ exploite les graphes Hierarchical Navigable Small World (HNSW) avec la quantification résiduelle de produit (PRQ), offrant une méthode d'indexation vectorielle avancée qui vous permet d'ajuster finement le compromis entre la taille de l'index et la précision. La PRQ va au-delà de la quantification par produit (PQ) traditionnelle en introduisant une étape de quantification résiduelle (RQ) pour capturer des informations supplémentaires, ce qui permet d'obtenir une plus grande précision ou des index plus compacts par rapport aux méthodes purement basées sur la PQ. Toutefois, les étapes supplémentaires peuvent entraîner une surcharge de calcul lors de la construction de l'index et de la recherche.

Vue d'ensemble

HNSW_PRQ combine deux techniques d'indexation : HSNW pour une navigation rapide basée sur les graphes et PRQ pour une compression vectorielle efficace.

HNSW

HNSW construit un graphe multicouche où chaque nœud correspond à un vecteur de l'ensemble de données. Dans ce graphe, les nœuds sont connectés en fonction de leur similarité, ce qui permet de parcourir rapidement l'espace de données. La structure hiérarchique permet à l'algorithme de recherche de réduire le nombre de voisins candidats, ce qui accélère considérablement le processus de recherche dans les espaces à haute dimension.

Pour plus d'informations, voir HNSW.

PRQ

PRQ est une approche de compression vectorielle en plusieurs étapes qui combine deux techniques complémentaires : PQ et RQ. En divisant d'abord un vecteur de haute dimension en sous-vecteurs plus petits (via PQ) et en quantifiant ensuite toute différence restante (via RQ), PRQ permet d'obtenir une représentation compacte mais précise des données d'origine.

La figure suivante illustre son fonctionnement.

Hnsw Prq

1. Quantification du produit (PQ)

   Dans cette phase, le vecteur original est divisé en sous-vecteurs plus petits, et chaque sous-vecteur est mis en correspondance avec son centroïde le plus proche dans un livre de codes appris. Ce mappage réduit considérablement la taille des données mais introduit une certaine erreur d'arrondi puisque chaque sous-vecteur est approximé par un seul centroïde. Pour plus de détails, voir IVF_PQ.

2. Quantification résiduelle (RQ)

   Après l'étape PQ, RQ quantifie le résidu - la différence entre le vecteur original et son approximation basée sur PQ - en utilisant des livres de codes supplémentaires. Comme ce résidu est généralement beaucoup plus petit, il peut être codé plus précisément sans que cela n'entraîne une augmentation importante de l'espace de stockage.

   Le paramètre nrq détermine le nombre de fois que ce résidu est quantifié de manière itérative, ce qui vous permet d'affiner l'équilibre entre l'efficacité et la précision de la compression.

3. Représentation finale de la compression

   Une fois que RQ a fini de quantifier le résidu, les codes entiers de PQ et de RQ sont combinés en un seul index compressé. En capturant des détails raffinés que PQ seul pourrait manquer, RQ améliore la précision sans entraîner une augmentation significative de l'espace de stockage. C'est cette synergie entre PQ et RQ qui définit le PRQ.

HNSW + PRQ

En combinant HNSW et PRQ, HNSW_PRQ conserve la recherche rapide basée sur les graphes de HNSW tout en tirant parti de la compression en plusieurs étapes de PRQ. Le flux de travail se présente comme suit :

1. Compression des données : Chaque vecteur est d'abord transformé par PQ en une représentation grossière, puis les résidus sont quantifiés par RQ pour être affinés. Le résultat est un ensemble de codes compacts représentant chaque vecteur.

2. Construction du graphique : Les vecteurs compressés (y compris les codes PQ et RQ) constituent la base de la construction du graphe HNSW. Les données étant stockées sous une forme compacte, le graphe nécessite moins de mémoire et la navigation est accélérée.

3. Recherche de candidats : Pendant la recherche, HNSW utilise les représentations comprimées pour parcourir le graphe et récupérer un ensemble de candidats. Cela permet de réduire considérablement le nombre de vecteurs à examiner.

4. Affinage des résultats (facultatif) : Les résultats initiaux des candidats peuvent être affinés pour une meilleure précision, en fonction des paramètres suivants :

   • refine: Contrôle si cette étape d'affinage est activée. Lorsqu'il est défini sur true, le système recalcule les distances à l'aide de représentations plus précises ou non compressées.

   • refine_type: Spécifie le niveau de précision des données utilisées pendant l'affinage (par exemple, SQ6, SQ8, BF16). Un choix de précision plus élevé, tel que FP32, peut donner des résultats plus précis, mais nécessite plus de mémoire. La précision doit être supérieure à celle de l'ensemble de données compressées d'origine de sq_type.

   • refine_k: Agit comme un facteur d'agrandissement. Par exemple, si votre top k est 100 et que refine_k est 2, le système reclasse les 200 premiers candidats et renvoie les 100 meilleurs, ce qui améliore la précision globale.

Pour obtenir la liste complète des paramètres et des valeurs valides, reportez-vous à la section Paramètres de l'index.

Création d'un index

Pour construire un index HNSW_PRQ sur un champ de vecteurs dans Milvus, utilisez la méthode add_index(), en spécifiant les paramètres index_type, metric_type et d'autres paramètres pour l'index.

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
)

Dans cette configuration :

• index_type: Le type d'index à construire. Dans cet exemple, la valeur est HNSW_PQ.

• metric_type: La méthode utilisée pour calculer la distance entre les vecteurs. Les valeurs prises en charge sont COSINE, L2 et IP. Pour plus d'informations, reportez-vous à la section Types de métriques.

• params: Options de configuration supplémentaires pour la construction de l'index. Pour plus d'informations, reportez-vous à la section Paramètres de construction de l'index.

Une fois les paramètres de l'index configurés, vous pouvez créer l'index en utilisant directement la méthode create_index() ou en transmettant les paramètres de l'index dans la méthode create_collection. Pour plus d'informations, reportez-vous à la section Créer une collection.

Recherche sur l'index

Une fois l'index construit et les entités insérées, vous pouvez effectuer des recherches de similarité sur l'index.

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
)

Dans cette configuration :

• params: Options de configuration supplémentaires pour la recherche sur l'index. Pour plus de détails, voir Paramètres de recherche spécifiques à l'index.

Paramètres de l'index

Cette section présente une vue d'ensemble des paramètres utilisés pour construire un index et effectuer des recherches dans l'index.

Paramètres de construction d'index

Le tableau suivant répertorie les paramètres qui peuvent être configurés sur params lors de la création d'un index.

	Paramètre	Description de l'index	Plage de valeurs	Suggestion de réglage
HNSW	M	Nombre maximal de connexions （ou d'arêtes) que chaque nœud peut avoir dans le graphe, y compris les arêtes sortantes et entrantes. Ce paramètre affecte directement la construction de l'index et la recherche.	Type: Integer (nombre entier) Plage: [2, 2048] Valeur par défaut: 30 (jusqu'à 30 arêtes sortantes et 30 arêtes entrantes par nœud)	Une valeur plus élevée de M entraîne généralement une plus grande précision, mais augmente la charge de mémoire et ralentit à la fois la construction de l'index et la recherche. Envisagez d'augmenter M pour les ensembles de données de grande dimensionnalité ou lorsqu'un rappel élevé est crucial. Pensez à diminuer M lorsque l'utilisation de la mémoire et la vitesse de recherche sont des préoccupations majeures. Dans la plupart des cas, nous vous recommandons de définir une valeur comprise dans cette fourchette : [5, 100].
	efConstruction	Un plus grand nombre de candidats est évalué pour chaque nouvel élément, mais le nombre maximum de connexions réellement établies est toujours limité par M.	Type: Integer (nombre entier) Plage: [1, int_max] Valeur par défaut: 360	Une valeur plus élevée de efConstruction se traduit généralement par un index plus précis, étant donné que davantage de connexions potentielles sont explorées. Cependant, cela entraîne également un allongement du temps d'indexation et une utilisation accrue de la mémoire lors de la construction. Envisagez d'augmenter efConstruction pour améliorer la précision, en particulier dans les scénarios où le temps d'indexation est moins critique. Pensez à diminuer efConstruction pour accélérer la construction de l'index lorsque les ressources sont limitées. Dans la plupart des cas, nous vous recommandons de définir une valeur comprise dans cette fourchette : [50, 500].
PRQ	m	Nombre de sous-vecteurs (utilisés pour la quantification) à diviser en chaque vecteur de haute dimension au cours du processus de quantification.	Type: Entier Plage: [1, 65536] Valeur par défaut: Aucune	Une valeur plus élevée de m peut améliorer la précision, mais elle augmente également la complexité du calcul et l'utilisation de la mémoire. m doit être un diviseur de la dimension du vecteur(D) pour garantir une décomposition correcte. Une valeur couramment recommandée est m = D/2. Dans la plupart des cas, nous vous recommandons de choisir une valeur comprise dans cet intervalle : [D/8, D].
	nbits	Le nombre de bits utilisés pour représenter l'indice du centroïde de chaque sous-vecteur sous forme comprimée. Il détermine directement la taille de chaque livre de codes. Chaque livre de codes contiendra des centroïdes de 2nbits. Par exemple, si nbits est fixé à 8, chaque sous-vecteur sera représenté par un indice de centroïde de 8 bits. Cela permet d'avoir28 (256) centroïdes possibles dans le livre de codes pour ce sous-vecteur.	Type: Entier Plage: [1, 24] Valeur par défaut: 8	Une valeur plus élevée de nbits permet d'obtenir des livres de codes plus importants, ce qui peut conduire à des représentations plus précises des vecteurs d'origine. Dans la plupart des cas, nous vous recommandons de choisir une valeur comprise dans cette fourchette : [1, 16].
	nrq	Contrôle le nombre de sous-quantifieurs résiduels utilisés dans l'étape RQ. Un plus grand nombre de sous-quantificateurs permet d'obtenir une plus grande compression, mais peut entraîner une perte d'informations plus importante.	Type: Entier Plage: [1, 16] Valeur par défaut: 2	Une valeur plus élevée de nrq permet des étapes supplémentaires de sous-quantification résiduelle, ce qui peut conduire à une reconstruction plus précise des vecteurs originaux. Toutefois, cela implique également de stocker et de calculer davantage de sous-quantificateurs, ce qui se traduit par une taille d'index plus importante et un surcoût de calcul plus élevé.
	refine	Un indicateur booléen qui contrôle si une étape de raffinement est appliquée pendant la recherche. L'affinage consiste à reclasser les résultats initiaux en calculant les distances exactes entre le vecteur de la requête et les candidats.	Type: booléen : Plage booléenne : [true, false] Valeur par défaut: false	Définissez true si une grande précision est essentielle et que vous pouvez tolérer des temps de recherche légèrement plus lents. Utilisez false si la rapidité est une priorité et qu'un compromis mineur sur la précision est acceptable.
	refine_type	Cette précision doit être supérieure à celle des vecteurs compressés (définie par les paramètres m et nbits ).	Type: Plage:[ SQ6, SQ8, BF16, FP16, FP32 ] Valeur par défaut: Aucune	Utilisez FP32 pour une précision maximale avec un coût de mémoire plus élevé, ou SQ6/SQ8 pour une meilleure compression. BF16 et FP16 offrent une alternative équilibrée.

Paramètres de recherche spécifiques à l'index

Le tableau suivant répertorie les paramètres qui peuvent être configurés dans search_params.params lors d'une recherche dans l'index.

	Paramètre	Paramètre Description	Plage de valeurs	Suggestion de réglage
HNSW	ef	Contrôle l'étendue de la recherche lors de l'extraction des plus proches voisins. Il détermine le nombre de nœuds visités et évalués en tant que plus proches voisins potentiels. Ce paramètre n'affecte que le processus de recherche et s'applique exclusivement à la couche inférieure du graphe.	Type: Entier Portée: [1, int_max] Valeur par défaut: limit (TopK plus proches voisins à retourner)	Une valeur plus élevée de ef permet généralement d'améliorer la précision de la recherche, car davantage de voisins potentiels sont pris en compte. Envisagez d'augmenter ef lorsqu'il est essentiel d'obtenir un rappel élevé et que la vitesse de recherche n'est pas une préoccupation majeure. Pensez à diminuer ef pour privilégier les recherches plus rapides, en particulier dans les scénarios où une légère réduction de la précision est acceptable. Dans la plupart des cas, nous vous recommandons de fixer une valeur comprise dans cette fourchette : [K, 10K].
PRQ	refine_k	Facteur d'agrandissement qui contrôle le nombre de candidats supplémentaires examinés au cours de l'étape d'affinage (reranking), par rapport aux K premiers résultats demandés.	Type: Flottant Plage: [1, float_max) Valeur par défaut: 1	Des valeurs élevées de refine_k peuvent améliorer le rappel et la précision, mais augmentent également le temps de recherche et l'utilisation des ressources. Une valeur de 1 signifie que le processus d'affinement ne prend en compte que les K premiers résultats.