IVF_RABITQCompatible with Milvus 2.6.x

L'index IVF_RABITQ est un algorithme d'indexation basé sur la quantification binaire qui quantifie les vecteurs FP32 en représentations binaires. Cet index offre une efficacité de stockage exceptionnelle avec un taux de compression de 1 pour 32 tout en maintenant des taux de rappel relativement bons. Il prend en charge le raffinement optionnel pour obtenir un meilleur rappel au prix d'un stockage supplémentaire, ce qui en fait un substitut polyvalent à IVF_SQ8 et IVF_FLAT dans les scénarios où la mémoire est limitée.

Vue d'ensemble

IVF_RABITQ signifie Inverted File with RaBitQ quantization (fichier inversé avec quantification RaBitQ), combinant deux techniques puissantes pour une recherche vectorielle et un stockage efficaces.

FIV

Lefichier inversé (IVF) organise l'espace vectoriel en régions gérables à l'aide du regroupement par k-moyennes. Chaque groupe est représenté par un centroïde, qui sert de point de référence pour les vecteurs de ce groupe. Cette approche de regroupement réduit l'espace de recherche en permettant à l'algorithme de se concentrer uniquement sur les groupes les plus pertinents lors du traitement de la requête.

Pour en savoir plus sur les détails techniques de l'IVF, reportez-vous à IVF_FLAT.

RaBitQ

RaBitQ est une méthode de quantification binaire de pointe avec des garanties théoriques, introduite dans l'article de recherche "RaBitQ : Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search" par Jianyang Gao et Cheng Long.

RaBitQ introduit plusieurs concepts innovants :

Encodage de l'information angulaire: Contrairement au codage spatial traditionnel, RaBitQ code l'information angulaire par normalisation vectorielle. Dans IVF_RABITQ, les vecteurs de données sont normalisés par rapport à leur centroïde IVF le plus proche, ce qui améliore la précision du processus de quantification.

Fondement théorique: La formule de base de l'approximation de la distance est la suivante

$$\lVert \mathbf{o_r} - \mathbf{q_r} \rVert^2 \approx \lVert \mathbf{o_r} - \mathbf{c_o} \rVert^2 + \lVert \mathbf{q_r} - \mathbf{c_o} \rVert^2 - 2 \cdot C(\mathbf{o_r}, \mathbf{c_o}) \cdot \langle \tilde{\mathbf{o}}, \mathbf{q_r} - \mathbf{c_o} \rangle + C_1(\mathbf{o_r}, \mathbf{c_o})$$

Où :

• $or\mathbf{o_r}$ or est un vecteur de données de l'ensemble de données.
• $qr\mathbf{q_r}$ qr est un vecteur de requête
• $co\mathbf{c_o}$ co est le vecteur centroïde IVF le plus proche de $or\mathbf{o_r}$ o r
• $C(\mathbf{o_r}, \mathbf{c_o})$ C$(\mathbf{o}$r, co ) et $C_1(\mathbf{o_r}, \mathbf{c_o})$ C ${}_{}(o$ r, c o ) sont des constantes précalculées.
• $o~\tilde{\mathbf{o}}$ ~ est le vecteur binaire quantifié stocké dans l'index
• $\tilde{\mathbf{o}}, \mathbf{q_r} - \mathbf{c_o} \rangle$ o ~$,$ q${}_{}-$ c${}_{}⟩$ représente l'opération de point-produit

Efficacité du calcul: La nature binaire de $o~\tilde{\mathbf{o}}$ ~ rend les calculs de distance extrêmement rapides, bénéficiant notamment des architectures CPU modernes avec des instructions AVX-512 VPOPCNTDQ dédiées sur les processeurs Intel Ice Lake+ ou AMD Zen 4+.

Améliorations algorithmiques: RaBitQ s'intègre efficacement aux techniques établies telles que l'approcheFastScan et les rotations aléatoires pour améliorer les performances.

IVF + RaBitQ

L'indice IVF_RABITQ combine le clustering efficace d'IVF avec la quantification binaire avancée de RaBitQ :

1. Filtrage grossier: IVF partitionne l'espace vectoriel en clusters, réduisant ainsi de manière significative l'étendue de la recherche en se concentrant sur les régions de clusters les plus pertinentes.

2. Quantification binaire: Au sein de chaque grappe, RaBitQ compresse les vecteurs en représentations binaires tout en préservant les relations de distance essentielles grâce à des garanties théoriques.

3. Raffinement optionnel: Lorsqu'il est activé, l'index stocke des données affinées supplémentaires en utilisant des formats de précision supérieure (SQ6, SQ8, FP16, BF16 ou FP32) pour améliorer les taux de rappel au prix d'une augmentation de l'espace de stockage.

Milvus met en œuvre IVF_RABITQ à l'aide des chaînes d'usine FAISS suivantes :

• Avec raffinement : "RR({dim}),IVF{nlist},RaBitQ,Refine({refine_index})"
• Sans raffinement : "RR({dim}),IVF{nlist},RaBitQ"

Construire un index

Pour construire un index IVF_RABITQ sur un champ de vecteurs dans Milvus, utilisez la méthode add_index(), en spécifiant les paramètres index_type, metric_type et des paramètres supplémentaires 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="IVF_RABITQ", # 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={
        "nlist": 1024, # Number of clusters for the index
        "refine": True, # Enable refinement for higher recall
        "refine_type": "SQ8" # Refinement data format
    } # Index building params
)

Dans cette configuration :

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

• 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": {
        "nprobe": 128, # Number of clusters to search
        "rbq_query_bits": 0, # Query vector quantization bits
        "refine_k": 1 # Refinement 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 donne un aperçu des paramètres utilisés pour construire un index et effectuer des recherches sur l'index.

Paramètres de construction d'index

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

	Paramètre	Description de l'index	Plage de valeurs	Suggestion de réglage
IVF	nlist	Nombre de grappes à créer à l'aide de l'algorithme k-means lors de la construction de l'index. Chaque grappe, représentée par un centroïde, stocke une liste de vecteurs. L'augmentation de ce paramètre réduit le nombre de vecteurs dans chaque grappe, créant ainsi des partitions plus petites et plus ciblées.	Type: Entier Plage de valeurs: [1, 65536] Valeur par défaut: 128	Les valeurs plus élevées de nlist améliorent le rappel en créant des grappes plus fines, mais augmentent le temps de construction de l'index. Optimisez en fonction de la taille du jeu de données et des ressources disponibles. Dans la plupart des cas, nous vous recommandons de définir une valeur comprise dans cet intervalle : [32, 4096].
RaBitQ	refine	Active le processus d'affinage et stocke les données affinées.	Type: Booléen Plage: [true, false] Valeur par défaut: false	La valeur par défaut est true si un taux de rappel de plus de 0,9 est nécessaire. L'activation de l'affinage améliore la précision mais augmente les besoins en stockage et le temps de construction de l'index.
	refine_type	Définit la représentation des données utilisée pour l'affinage lorsque refine est activé.	Type: Chaîne Plage: [SQ6, SQ8, FP16, BF16, FP32] Valeur par défaut: Aucune	Les valeurs énumérées sont présentées dans l'ordre suivant : taux de rappel croissant, QPS décroissant et taille de stockage croissante. SQ8 est recommandé comme point de départ, car il offre un bon équilibre entre la précision et l'utilisation des ressources.

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

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

	Paramètre	Description du paramètre	Plage de valeurs	Suggestion de réglage
IVF	nprobe	Le nombre de grappes à rechercher pour les candidats. Des valeurs plus élevées permettent de rechercher davantage de grappes, ce qui améliore le rappel en élargissant le champ de recherche, mais au prix d'une latence accrue de la requête.	Type: Entier Plage de valeurs: [1, nlist] Valeur par défaut: 8	L'augmentation de cette valeur améliore la mémorisation mais peut ralentir la recherche. Réglez nprobe proportionnellement à nlist pour équilibrer la vitesse et la précision. Dans la plupart des cas, nous vous recommandons de définir une valeur comprise dans cette fourchette : [1, nlist].
RaBitQ	rbq_query_bits	Définit si une quantification scalaire supplémentaire d'un vecteur de requête est appliquée. Si la valeur est 0, la requête est utilisée sans quantification. Si la valeur est comprise entre [1 et 8], la requête est prétraitée à l'aide d'une quantification scalaire sur n bits.	Type: Entier Plage de valeurs: [0, 8] Valeur par défaut: 0	La valeur par défaut de 0 offre un taux de rappel maximal mais des performances plus lentes. Nous recommandons de tester les valeurs 0, 8, et 6, car elles fournissent des taux de rappel similaires, 6 étant la plus rapide. Utilisez des valeurs plus petites pour des exigences de rappel plus élevées.
	refine_k	Le processus d'affinage utilise une quantification de meilleure qualité pour sélectionner le nombre nécessaire de plus proches voisins à partir d'un ensemble de candidats refine_k fois plus important choisi à l'aide de IVF_RABITQ.	Type: Flottant Plage: [1, float_max) Valeur par défaut: 1	Des valeurs plus élevées de refine_k diminuent le QPS mais augmentent le taux de rappel. Commencez par 1 et testez les valeurs 2, 3, 4, et 5 pour trouver le compromis optimal entre QPS et rappel pour votre ensemble de données.