Index en mémoire

Indices pour les intégrations en virgule flottante

Pour les encastrements en virgule flottante à 128 dimensions (vecteurs), l'espace de stockage qu'ils occupent est de 128 * la taille de la virgule flottante = 512 octets. Les mesures de distance utilisées pour les enregistrements en virgule flottante sont la distance euclidienne (L2) et le produit intérieur (IP).

Ces types d'index comprennent FLAT, IVF_FLAT, IVF_PQ, IVF_SQ8, HNSW, HNSW_SQ, HNSW_PQ, HNSW_PRQ, et SCANN pour les recherches ANN basées sur l'unité centrale.

FLAT

Pour les applications de recherche de similarités vectorielles qui exigent une précision parfaite et dépendent d'ensembles de données relativement petits (à l'échelle du million), l'index FLAT est un bon choix. FLAT ne compresse pas les vecteurs et est le seul index qui peut garantir des résultats de recherche exacts. Les résultats de FLAT peuvent également servir de point de comparaison pour les résultats produits par d'autres index dont le taux de rappel est inférieur à 100 %.

FLAT est précis parce qu'il adopte une approche exhaustive de la recherche, ce qui signifie que pour chaque requête, l'entrée cible est comparée à tous les vecteurs d'un ensemble de données. Cela fait de FLAT l'index le plus lent de notre liste, et il est mal adapté à l'interrogation de données vectorielles massives. Aucun paramètre n'est requis pour l'index FLAT dans Milvus et son utilisation ne nécessite pas de formation aux données.

• Paramètres de recherche

  Paramètre	Description	Distance
  metric_type	[Facultatif] La métrique de distance choisie.	Voir Métriques prises en charge.

IVF_FLAT

IVF_FLAT divise les données vectorielles en nlist unités de grappes, puis compare les distances entre le vecteur d'entrée cible et le centre de chaque grappe. En fonction du nombre de grappes que le système est configuré pour interroger (nprobe), les résultats de la recherche de similarité sont renvoyés sur la base des comparaisons entre l'entrée cible et les vecteurs dans la ou les grappes les plus similaires uniquement - ce qui réduit considérablement le temps d'interrogation.

En ajustant nprobe, un équilibre idéal entre la précision et la vitesse peut être trouvé pour un scénario donné. Les résultats du test de performance IVF_FLAT montrent que le temps d'interrogation augmente fortement à mesure que le nombre de vecteurs d'entrée cibles (nq) et le nombre de grappes à rechercher (nprobe) augmentent.

IVF_FLAT est l'index IVF le plus basique, et les données encodées stockées dans chaque unité sont cohérentes avec les données originales.

• Paramètres de construction de l'index

  Paramètre	Description de l'indice	Plage de valeurs	Valeur par défaut
  nlist	Nombre d'unités de cluster	[1, 65536]	128

• Paramètres de recherche

  • Recherche commune

    Paramètre	Description de la recherche	Plage de valeurs	Valeur par défaut
    nprobe	Nombre d'unités à interroger	[1, nlist]	8

  • Recherche par plage

    Paramètre	Description de la plage	Plage	Valeur par défaut
    max_empty_result_buckets	Nombre maximal de godets ne donnant aucun résultat de recherche. Il s'agit d'un paramètre de recherche par plage et il met fin au processus de recherche lorsque le nombre de godets vides consécutifs atteint la valeur spécifiée. L'augmentation de cette valeur peut améliorer le taux de rappel au prix d'un allongement du temps de recherche.	[1, 65535]	2

IVF_SQ8

IVF_FLAT n'effectue aucune compression, de sorte que les fichiers d'index qu'il produit sont à peu près de la même taille que les données vectorielles brutes non indexées d'origine. Par exemple, si l'ensemble de données SIFT 1B d'origine pèse 476 Go, les fichiers d'index IVF_FLAT seront légèrement plus petits (~470 Go). Le chargement de tous les fichiers d'index en mémoire consommera 470 Go d'espace de stockage.

Lorsque les ressources disque, CPU ou mémoire GPU sont limitées, IVF_SQ8 est une meilleure option qu'IVF_FLAT. Ce type d'index peut convertir chaque FLOAT (4 octets) en UINT8 (1 octet) en effectuant une quantification scalaire (SQ). Cela permet de réduire la consommation de mémoire du disque, du CPU et du GPU de 70 à 75 %. Pour l'ensemble de données 1B SIFT, les fichiers d'index IVF_SQ8 ne nécessitent que 140 Go de stockage.

• Paramètres de construction de l'index

  Paramètre	Description de l'indice	Fourchette
  nlist	Nombre d'unités de cluster	[1, 65536]

• Paramètres de recherche

  • Recherche commune

    Paramètre	Description de la recherche	Plage de valeurs	Valeur par défaut
    nprobe	Nombre d'unités à interroger	[1, nlist]	8

  • Recherche par plage

    Paramètre	Description de la plage	Plage	Valeur par défaut
    max_empty_result_buckets	Nombre maximal de godets ne donnant aucun résultat de recherche. Il s'agit d'un paramètre de recherche par plage et il met fin au processus de recherche lorsque le nombre de godets vides consécutifs atteint la valeur spécifiée. L'augmentation de cette valeur peut améliorer le taux de rappel au prix d'un allongement du temps de recherche.	[1, 65535]	2

IVF_PQ

PQ (Product Quantization) décompose uniformément l'espace vectoriel haute dimension original en produits cartésiens d'espaces vectoriels basse dimension m, puis quantifie les espaces vectoriels basse dimension décomposés. Au lieu de calculer les distances entre le vecteur cible et le centre de toutes les unités, la quantification par produit permet de calculer les distances entre le vecteur cible et le centre de regroupement de chaque espace de faible dimension, ce qui réduit considérablement la complexité temporelle et spatiale de l'algorithme.

IVF_PQ effectue le regroupement de l'index IVF avant de quantifier le produit des vecteurs. Son fichier d'index est encore plus petit que IVF_SQ8, mais il entraîne également une perte de précision lors de la recherche de vecteurs.

• Paramètres de construction d'index

  Paramètre	Description	Fourchette
  nlist	Nombre d'unités de cluster	[1, 65536]
  m	Nombre de facteurs de quantification du produit	dim mod m == 0
  nbits	[Facultatif] Nombre de bits dans lesquels chaque vecteur de faible dimension est stocké.	[1, 64] (8 par défaut)

• Paramètres de recherche

  • Recherche commune

    Paramètre	Description de la recherche	Plage de valeurs	Valeur par défaut
    nprobe	Nombre d'unités à interroger	[1, nlist]	8

  • Recherche par plage

    Paramètre	Description de la plage	Plage	Valeur par défaut
    max_empty_result_buckets	Nombre maximal de godets ne donnant aucun résultat de recherche. Il s'agit d'un paramètre de recherche par plage et il met fin au processus de recherche lorsque le nombre de godets vides consécutifs atteint la valeur spécifiée. L'augmentation de cette valeur peut améliorer le taux de rappel au prix d'un allongement du temps de recherche.	[1, 65535]	2

SCANN

ScaNN (Scalable Nearest Neighbors) est similaire à IVF_PQ en termes de regroupement de vecteurs et de quantification de produits. Ce qui les différencie, ce sont les détails de la mise en œuvre de la quantification du produit et l'utilisation de SIMD (Single-Instruction / Multi-data) pour un calcul efficace.

• Paramètres de construction de l'index

  Paramètre	Description de l'indice	Fourchette
  nlist	Nombre d'unités de cluster	[1, 65536]
  with_raw_data	Inclure ou non les données brutes dans l'index	True ou False. La valeur par défaut est True.

  Contrairement à IVF_PQ, les valeurs par défaut s'appliquent à m et nbits pour optimiser les performances.

• Paramètres de recherche

  • Recherche commune

    Paramètre	Description de la recherche	Plage de valeurs	Valeur par défaut
    nprobe	Nombre d'unités à interroger	[1, nlist]
    reorder_k	Nombre d'unités candidates à interroger	[top_k, ∞]	top_k

  • Plage de recherche

    Paramètre	Description	Plage	Valeur par défaut
    max_empty_result_buckets	Nombre maximal de godets ne donnant aucun résultat de recherche. Il s'agit d'un paramètre de recherche par plage et il met fin au processus de recherche lorsque le nombre de godets vides consécutifs atteint la valeur spécifiée. L'augmentation de cette valeur peut améliorer le taux de rappel au prix d'un allongement du temps de recherche.	[1, 65535]	2

HNSW

HNSW (Hierarchical Navigable Small World Graph) est un algorithme d'indexation basé sur les graphes. Il construit une structure de navigation multicouche pour une image selon certaines règles. Dans cette structure, les couches supérieures sont plus clairsemées et les distances entre les nœuds sont plus grandes ; les couches inférieures sont plus denses et les distances entre les nœuds sont plus étroites. La recherche commence par la couche la plus haute, trouve le nœud le plus proche de la cible dans cette couche, puis passe à la couche suivante pour commencer une nouvelle recherche. Après plusieurs itérations, elle peut rapidement s'approcher de la position de la cible.

Afin d'améliorer les performances, HNSW limite le degré maximal des nœuds de chaque couche du graphe à M. En outre, vous pouvez utiliser efConstruction (lors de la construction de l'index) ou ef (lors de la recherche des cibles) pour spécifier une plage de recherche.

• Paramètres de construction de l'index

  Paramètre	Description de l'index	Plage	Valeur par défaut
  M	M définit le nombre maximal de connexions sortantes dans le graphique. Un M plus élevé entraîne une plus grande précision/temps d'exécution à ef/efConstruction fixe.	[2, 2048]	Aucune
  efConstruction	ef_construction contrôle le compromis entre la vitesse de recherche et la vitesse de construction de l'index. L'augmentation du paramètre efConstruction peut améliorer la qualité de l'index, mais elle tend également à allonger le temps d'indexation.	[1, int_max]	Aucun

• Paramètres de recherche

  Paramètre	Description de la recherche	Plage de valeurs	Valeur par défaut
  ef	Paramètre contrôlant le compromis temps de recherche/précision. Une valeur plus élevée ( ef ) permet une recherche plus précise mais plus lente.	[top_k, int_max]	Aucune

HNSW_SQ

La quantification scalaire (SQ) est une technique utilisée pour diviser les données en virgule flottante en un ensemble fini de valeurs basées sur leur magnitude. Par exemple, SQ6 représente la quantification en (2^6 = 64) valeurs discrètes, où chaque nombre à virgule flottante est codé sur 6 bits. De même, SQ8 quantifie les données en (2^8 = 256) valeurs discrètes, chaque nombre à virgule flottante étant représenté par 8 bits. Cette quantification réduit l'empreinte mémoire tout en préservant la structure essentielle des données pour un traitement efficace.

Combiné à SQ, HNSW_SQ offre un compromis contrôlable entre la taille de l'index et la précision, tout en maintenant des performances élevées en termes de nombre de requêtes par seconde (QPS). Par rapport à la méthode HNSW standard, il en résulte une augmentation modeste du temps de construction de l'index.

• Paramètres de construction de l'index

  Paramètre	Description de l'index	Plage de valeurs	Valeur par défaut
  M	M définit le nombre maximal de connexions sortantes dans le graphique. Plus M est élevé, plus la précision/le temps d'exécution est important(e) à ef/efConstruction fixe.	[2, 2048]	Aucune
  efConstruction	ef_construction contrôle le compromis entre la vitesse de recherche et la vitesse de construction de l'index. L'augmentation du paramètre efConstruction peut améliorer la qualité de l'index, mais elle tend également à allonger le temps d'indexation.	[1, int_max]	Aucun
  sq_type	Type de quantificateur scalaire.	SQ6,SQ8, BF16, FP16	SQ8
  refine	Si les données affinées sont réservées pendant la construction de l'index.	true, false	false
  refine_type	Le type de données de l'index affiné.	SQ6, SQ8, BF16, FP16, FP32	Aucun

• Paramètres de recherche

  Paramètre	Description de la recherche	Plage de valeurs	Valeur par défaut
  ef	Paramètre contrôlant le compromis temps de recherche/précision. Une valeur plus élevée ( ef ) permet une recherche plus précise mais plus lente.	[top_k, int_max]	Aucun
  refine_k	Le facteur d'agrandissement de refine par rapport à k.	[1, float_max)	1

HNSW_PQ

L'idée de base de PQ est de diviser le vecteur en m sous-vecteurs, dont chacun trouvera 2^{nbits} centroïdes sur la base de kmeans, et chaque sous-vecteur sélectionnera le centroïde le plus proche comme son sous-vecteur approximatif. Nous enregistrons ensuite tous les centriodes, de sorte que chaque sous-vecteur peut être codé sous la forme nbits, et un vecteur flottant de longueur dim peut être codé sous la forme de m ⋅ nbits bits.

Combiné avec PQ, HNSW_PQ offre un compromis contrôlable entre la taille de l'index et la précision, mais il a une valeur QPS plus faible et un taux de rappel plus élevé que HNSW_SQ pour le même taux de compression. Par rapport à HNSW_SQ, la construction de l'index prend plus de temps.

• Paramètres de construction de l'index

  Paramètre	Description	Plage de valeurs	Valeur par défaut
  M	M définit le nombre maximal de connexions sortantes dans le graphique. Un M plus élevé entraîne une plus grande précision/temps d'exécution à ef/efConstruction fixe.	[2, 2048]	Aucune
  efConstruction	ef_construction contrôle le compromis entre la vitesse de recherche et la vitesse de construction de l'index. L'augmentation du paramètre efConstruction peut améliorer la qualité de l'index, mais elle tend également à allonger le temps d'indexation.	[1, int_max]	Aucun
  m	Le nombre de groupes de sous-vecteurs à diviser le vecteur.	[1, 65536]	32
  nbits	Le nombre de bits dans lesquels chaque groupe de sous-vecteurs est quantifié.	[1, 24]	8
  refine	Si les données affinées sont réservées lors de la construction de l'index.	true, false	false
  refine_type	Le type de données de l'index affiné.	SQ6, SQ8, BF16, FP16, FP32	Aucun

• Paramètres de recherche

  Paramètre	Description de la recherche	Plage de valeurs	Valeur par défaut
  ef	Paramètre contrôlant le compromis temps de recherche/précision. Une valeur plus élevée ( ef ) permet une recherche plus précise mais plus lente.	[top_k, int_max]	Aucun
  refine_k	Le facteur d'agrandissement de refine par rapport à k.	[1, float_max)	1

HNSW_PRQ

PRQ est similaire à PQ et divise également le vecteur en groupes m. Chaque sous-vecteur sera codé comme nbits. Après avoir effectué une quantification pq, il calcule le résidu entre le vecteur et le vecteur quantifié pq, et applique la quantification pq au vecteur résiduel. Un total de nrq quantifications pq complètes sera effectué, de sorte qu'un vecteur flottant de longueur dim sera codé comme m ⋅ nbits ⋅ nrq bits.

Combiné à un quantificateur résiduel de produit (PRQ), le HNSW_PRQ offre un compromis contrôlable encore plus élevé entre la taille de l'index et la précision. Il a une valeur QPS presque équivalente et un taux de rappel plus élevé que HNSW_PQ pour le même taux de compression. Par rapport à HNSW_PQ, le temps de construction de l'index peut être multiplié par plusieurs fois.

• Paramètres de construction de l'index

  Paramètre	Description	Plage de valeurs	Valeur par défaut
  M	M définit le nombre maximal de connexions sortantes dans le graphique. Un M plus élevé entraîne une plus grande précision/temps d'exécution à ef/efConstruction fixe.	[2, 2048]	Aucune
  efConstruction	ef_construction contrôle le compromis entre la vitesse de recherche et la vitesse de construction de l'index. L'augmentation du paramètre efConstruction peut améliorer la qualité de l'index, mais elle tend également à allonger le temps d'indexation.	[1, int_max]	Aucun
  m	Le nombre de groupes de sous-vecteurs à diviser le vecteur.	[1, 65536]	32
  nbits	Le nombre de bits dans lesquels chaque groupe de sous-vecteurs est quantifié.	[1, 24]	8
  nrq	Le nombre de sous-quantificateurs résiduels.	[1, 16]	2
  refine	Si les données affinées sont réservées lors de la construction de l'index.	true, false	false
  refine_type	Le type de données de l'index affiné.	SQ6, SQ8, BF16, FP16, FP32	Aucun

• Paramètres de recherche

  Paramètre	Description de la recherche	Plage de valeurs	Valeur par défaut
  ef	Paramètre contrôlant le compromis temps de recherche/précision. Une valeur plus élevée ( ef ) permet une recherche plus précise mais plus lente.	[top_k, int_max]	Aucune
  refine_k	Le facteur d'agrandissement de refine par rapport à k.	[1, float_max)	1