Qu'est-ce que l'indexation vectorielle ? - Un guide complet 2024

Dans le domaine du développement de bases de données, la demande d'accès rapide et précis aux données a conduit à des méthodes d'indexation innovantes. Les tableaux traditionnels n'étant pas adaptés à la gestion de données à grande échelle, des systèmes plus structurés tels que les bases de données relationnelles sont entrés en jeu, intégrant des stratégies d'indexation avancées. Prenons l'exemple d'un supermarché, les produits des supermarchés sont méticuleusement triés dans des catégories distinctes telles que les fruits et légumes, les produits laitiers et les produits de boulangerie, rationalisant ainsi le processus d'achat en orientant les clients directement vers la section souhaitée. Cette méthode d'organisation physique reflète les principes de l'indexation numérique, selon laquelle les données sont classées efficacement pour faciliter un accès rapide.

L'indexation vectorielle est à la base de nombreuses applications modernes et améliore les interactions entre les utilisateurs sur les différentes plateformes. Par exemple, Netflix utilise l'indexation vectorielle pour affiner ses recommandations, garantissant ainsi aux spectateurs des films et des émissions correspondant à leurs goûts. Amazon exploite une technologie similaire pour personnaliser les suggestions de produits, améliorant ainsi les expériences d'achat en les adaptant au comportement des consommateurs. Dans le secteur de la santé, l'indexation vectorielle accélère la récupération des dossiers des patients, permettant ainsi des diagnostics plus rapides et plus précis. Les plateformes de réseaux sociaux comme Facebook exploitent cette technologie pour personnaliser les flux et les publicités, en donnant la priorité au contenu qui correspond aux préférences des utilisateurs. Ce déploiement stratégique de l'indexation vectorielle améliore considérablement l'efficacité et la satisfaction des utilisateurs, démontrant ainsi son rôle vital dans la transformation des données brutes en informations exploitables.

Que sont les intégrations vectorielles ?

Les intégrations vectorielles constituent une façon transformatrice de représenter les données, permettant aux machines de comprendre et de traiter plus efficacement diverses formes d'informations. Essentiellement, les intégrations convertissent des éléments complexes, qu'il s'agisse de mots, d'images ou de sons, en vecteurs numériques de taille fixe, qui capturent les caractéristiques essentielles des données.

Imaginez que vous essayez d'apprendre à un ordinateur à différencier les différents types de musique. En convertissant des chansons en intégrations basées sur des caractéristiques telles que le tempo, le rythme et l'instrumentation, chaque chanson devient un point dans un espace multidimensionnel. Les chansons présentant des caractéristiques similaires sont regroupées dans cet espace, un peu comme les différents genres peuvent être regroupés dans un magasin de musique. Cette disposition spatiale permet aux algorithmes de reconnaître facilement des modèles et des similitudes, ce qui est crucial pour des tâches telles que la recommandation musicale ou la classification des genres.

Dans un contexte plus quotidien, pensez aux intégrations, comme la compréhension de vos préférences par une application de réseau social. Sur la base des types de publications avec lesquels vous interagissez, l'application développe un « profil » numérique qui représente vos goûts et vos aversions. Il utilise ensuite ce profil pour décider du nouveau contenu à vous montrer, dans le but de présenter les publications proches de votre profil dans son espace multidimensionnel d'intégrations de contenu.

Comprendre les index vectoriels

L'indexation vectorielle joue un rôle crucial dans la gestion et la récupération de données de grande dimension stockées dans des espaces vectoriels. Mais d'abord, qu'est-ce qu'un espace vectoriel dans ce contexte ? Il s'agit essentiellement d'une construction mathématique dans laquelle chaque point représente une donnée distincte, telle que du texte, des images ou des sons, convertie en un format numérique appelé vecteur. Ces vecteurs capturent les caractéristiques essentielles des données, ce qui permet d'effectuer des calculs complexes.

• Transformation vectorielle: Le processus commence par la conversion des données brutes en vecteurs. Chaque vecteur quantifie les principales caractéristiques du contenu original, traduisant des informations complexes dans un langage que les systèmes informatiques peuvent comprendre et traiter efficacement.
• ‍Construction de l'indice: Une fois les données transformées en vecteurs, l'étape suivante consiste à créer un index pour gérer ces vecteurs de manière systématique. Différents algorithmes sont utilisés pour optimiser le stockage et la récupération de ces vecteurs, réduisant ainsi efficacement l'espace de recherche et améliorant les performances.
• ‍Regroupement de vecteurs similaires: Des techniques telles que le clustering k-means, le Hierarchical Navigable Small World (HNSW) ou la quantification des produits sont utilisées pour organiser des vecteurs similaires en groupes. Le clustering K-means, par exemple, divise les vecteurs en groupes en fonction de leurs similitudes, rationalisant ainsi le processus de recherche en se concentrant uniquement sur les clusters pertinents lors d'une requête.
• ‍Recherche efficace: lorsqu'une requête est faite, par exemple lorsqu'un utilisateur recherche une image similaire à celle qu'il possède, le système d'indexation identifie rapidement le cluster contenant les vecteurs les plus similaires à la requête. Il effectue ensuite une recherche ciblée au sein de ce cluster, accélérant ainsi considérablement la récupération des résultats pertinents.

Grâce à ces étapes, l'indexation vectorielle facilite un accès rapide et précis à de vastes ensembles de données, transformant les données brutes en informations exploitables.

Techniques d'indexation vectorielle de base

Indices inversés :

Les index inversés sont une structure de données fondamentale largement utilisée dans les moteurs de recherche et les systèmes de recherche d'informations. Ils permettent d'interroger efficacement de grands ensembles de données en mappant le contenu à ses emplacements dans une base de données. Voici un aperçu détaillé du concept de base et de certains types spécifiques d'index inversés, y compris des variantes de la technique d'indexation des fichiers inversés (FIV) :

‍

Indexation anticipée :

Indexation inversée :

Exemple de base illustrant la différence entre l'indexation directe et l'indexation inversée

‍

Indice inversé de base :

À la base, un index inversé consiste en un dictionnaire où chaque mot ou terme est associé à une liste de documents dans lesquels ce terme apparaît. Il s'agit essentiellement d'une « inversion » de la relation document-mot normale, d'où son nom. Cette configuration accélère considérablement le processus de recherche de tous les documents contenant un mot particulier.

Variations et améliorations :

• Indices de position: Pour prendre en charge les requêtes de phrase et de proximité, il est souvent nécessaire de stocker non seulement les identificateurs de document (ID) où un mot apparaît, mais également les positions spécifiques dans ces documents. Cela permet au moteur de recherche de trouver rapidement des documents dans lesquels les mots apparaissent non seulement, mais le font dans un ordre spécifique ou à une certaine distance les uns des autres.
• ‍Informations sur la fréquence : Certaines implémentations stockent la fréquence de chaque mot dans chaque document. Cela peut être utile pour optimiser les plans d'exécution des requêtes, car les documents dont la fréquence des termes est plus élevée peuvent être considérés comme plus pertinents, en fonction de la requête.
• ‍Indices doubles: Certains systèmes gèrent deux listes inversées distinctes : une pour les numéros et les fréquences des documents, et une autre pour la position complète des mots. Les requêtes simples peuvent utiliser les listes les plus courtes, tandis que les recherches plus complexes impliquant la proximité peuvent utiliser les listes de positions détaillées.

Variantes du fichier inversé (FIV) :

• GONFLAGE : Utilise un modèle de stockage plat au sein de chaque cluster pour des opérations de recherche simplifiées et efficaces, particulièrement efficaces dans les ensembles de données de taille moyenne nécessitant une précision élevée.
• ‍IVFPQ (quantification du produit): Améliore l'efficacité en décomposant les vecteurs de grande dimension en sous-espaces plus petits qui sont quantifiés indépendamment, ce qui permet des recherches de similarité rapides et des besoins de stockage réduits.
• ‍IVFSQ (quantification scalaire) : Utilise la quantification scalaire pour simplifier le processus de codage en traitant chaque dimension séparément, réduisant ainsi la complexité informatique et les frais de stockage, ce qui est idéal pour les données de moindre dimension.

Techniques de compression :

• Codage à longueur variable: L'utilisation de méthodes telles que les entiers de longueur variable pour stocker les identifiants et les positions des documents peut réduire considérablement l'espace nécessaire.
• Codage Delta: En stockant uniquement la différence entre les numéros ou les positions des documents consécutifs, le codage delta permet de réduire davantage l'espace requis, car les différences sont souvent inférieures aux valeurs absolues.

Des structures avancées pour une efficacité accrue:

• Structure de la liste des groupes : Une adaptation de l'index inversé dans lequel les identificateurs de documents sont regroupés, améliorant ainsi l'efficacité lors de l'exécution d'opérations telles que l'intersection ou l'union, qui sont courantes dans le traitement des requêtes.

Cas d'utilisation et applications:

Les index inversés jouent un rôle essentiel non seulement dans les moteurs de recherche, mais également dans les systèmes traitant des données semi-structurées (comme les bases de données XML et RDF) et dans les moteurs de recherche graphiques utilisés sur les réseaux sociaux. L'efficacité de ces index a un impact direct sur les performances et l'évolutivité de ces systèmes.

Le petit monde navigable hiérarchique (HNSW)

Illustration de l'idée hiérarchique de la Nouvelle-Galles du Sud. La recherche commence à partir d'un élément de la couche supérieure (en rouge). Les flèches rouges indiquent la direction de l'algorithme gourmand entre le point d'entrée et la requête (en vert). Adapté de https://arxiv.org/abs/1603.09320

L'algorithme HNSW représente une approche avancée basée sur des graphiques pour l'indexation et la recherche de données de grande dimension. Il exploite efficacement une structure multicouche, s'inspirant des listes de raccourcis et des réseaux navigables de petite taille (NSW) pour optimiser à la fois le stockage et les opérations de recherche dans les bases de données.

Comprendre le HNSW :

• Ignorer la liste d'inspiration: Dans une liste à ignorer traditionnelle, les données sont organisées à plusieurs niveaux. Chaque niveau contient un sous-ensemble de données, la couche inférieure contenant tous les points de données et chaque couche successive sautant certains points de manière incrémentielle. Cette structure en couches permet des chemins de recherche efficaces en commençant par le haut et en les réduisant en fonction des comparaisons.
• ‍Petit monde navigable (Nouvelle-Galles du Sud): NSW apporte le concept de connexion de points de données (nœuds) dans un graphique basé sur la similitude, en utilisant un algorithme gourmand pour naviguer parmi les voisins les plus proches. Cela garantit l'efficacité des recherches, même dans des ensembles de données volumineux et complexes, en partant d'un nœud connu et en passant progressivement à des nœuds plus proches jusqu'à ce que le plus proche soit trouvé.

Comment fonctionne le HNSW:

• Structure graphique en couches: HNSW utilise un graphe en couches dans lequel chaque nœud est connecté à d'autres nœuds de la même couche ainsi qu'à des nœuds de la couche inférieure suivante. La couche supérieure comporte le moins de nœuds et sa densité augmente à mesure que les couches descendent. Cette configuration imite la stratégie de recherche efficace de la liste de raccourcis, mais elle est adaptée pour gérer la complexité des espaces de données de grande dimension.
• ‍Processus de recherche dans HNSW: Une recherche commence à la couche supérieure en examinant les nœuds connectés à un point de départ prédéfini et en se déplaçant vers le nœud le plus proche de la requête cible. La recherche progresse vers le bas à travers les couches, réduisant l'espace de recherche jusqu'à atteindre la couche la plus basse, qui contient tous les points de données. Cette méthode garantit que la recherche est approfondie et intègre les voisins les plus proches potentiels.

Variantes de HNSW:

• HNSWFLAT: Dans cette variante, les vecteurs bruts sont stockés directement dans les nœuds du graphe. Cette variante est simple et conserve les données d'origine mais nécessite plus d'espace de stockage.
• ‍HNSWSQ: Reprenant l'approche de la quantification scalaire dans IVFSQ, le HNSWSQ stocke les vecteurs dans un format quantifié, ce qui réduit les besoins de stockage et peut améliorer la vitesse de recherche au prix d'une légère diminution de la précision.

Cas d'utilisation et applications:

Le HNSW est particulièrement efficace pour les applications nécessitant un accès rapide à des éléments similaires dans de grands ensembles de données, tels que la récupération d'images, les systèmes de recommandation et d'autres scénarios impliquant des recherches de similarité complexes. Sa conception permet des requêtes évolutives et efficaces en minimisant les calculs de distance nécessaires pour trouver les voisins les plus proches, ce qui en fait un choix privilégié pour les systèmes traitant de grands volumes de données.

Hachage sensible à la localité (LSH)

Présentation de LSH :

Le hachage sensible à la localité rationalise la recherche des voisins les plus proches en utilisant des fonctions de hachage « sensibles » à la localité des données. Cela signifie que les vecteurs proches les uns des autres dans l'ensemble de données sont susceptibles d'être hachés dans le même « compartiment » ou compartiment dans la table de hachage.

Comment fonctionne le LSH :

• Fonction de hachage: LSH utilise un type spécifique de fonction de hachage qui regroupe des vecteurs proches dans le même compartiment de hachage. Ces fonctions sont conçues de telle sorte que la probabilité de collision (c'est-à-dire le hachage vers le même compartiment) soit plus élevée pour les éléments proches les uns des autres dans l'espace vectoriel.
• Construction de l'indice: Pendant la phase d'indexation, les intégrations vectorielles de l'ensemble de données sont hachées à l'aide de ces fonctions. Les vecteurs similaires se retrouvent dans le même compartiment, ce qui réduit la nécessité de rechercher les voisins les plus proches dans l'ensemble de données.
• ‍Traitement des requêtes: lorsqu'un vecteur de requête est soumis, LSH hache ce vecteur pour trouver le compartiment correspondant. La recherche des voisins les plus proches est alors limitée à ce compartiment uniquement. Le système calcule des métriques de similarité pour les vecteurs de ce compartiment, ce qui réduit considérablement le nombre de comparaisons nécessaires par rapport aux méthodes qui nécessitent une recherche dans l'ensemble de données.

Cas d'utilisation et applications :

Systèmes de recommandation: permet de trouver rapidement des éléments qui correspondent aux centres d'intérêt d'un utilisateur.

Récupération d'images : Recherche d'images visuellement similaires à une image de requête.

Détection des quasi-doublons: Identification de documents texte ou de fichiers multimédia similaires dans de grandes bases de données.

Quelques exemples d'applications LSH hiérarchiques. Adapté de https://arxiv.org/pdf/2204.11209

Certaines autres techniques d'indexation qui ne sont pas abordées ici sont Ball-Tree, KD-Tree (arbre dimensionnel K), R-Tree, Annoy (voisins les plus proches approximatifs Oh Yeah).

Conclusion

En conclusion, l'indexation vectorielle est un élément fondamental qui améliore les processus de récupération de données dans divers secteurs et applications. Qu'il s'agisse de services de streaming multimédia tels que Netflix qui optimisent leurs algorithmes de recommandation ou de géants du commerce électronique tels qu'Amazon qui améliorent l'expérience d'achat de leurs clients, l'utilisation stratégique de l'indexation vectorielle est cruciale pour traduire d'immenses volumes de données en informations personnalisées et exploitables. Les plateformes de santé et de réseaux sociaux tirent également parti de ces stratégies d'indexation sophistiquées pour fournir de meilleurs services et une meilleure pertinence du contenu, prouvant ainsi l'applicabilité et l'efficacité étendues de ces technologies.

Dans le cadre de l'exploration de l'indexation vectorielle, nous avons étudié diverses techniques telles que l'indice inversé, le Hierarchical Navigable Small World (HNSW) et le hachage sensible à la localité (LSH), chacune présentant des caractéristiques uniques adaptées à différentes structures de données et à différents besoins. Ces techniques rationalisent non seulement le processus de récupération des données, mais garantissent également l'évolutivité et l'efficacité, indispensables dans le monde actuel axé sur les données.

Alors que l'indexation vectorielle continue d'évoluer, il sera vital pour les développeurs, les data scientists et les entreprises de rester à jour avec ces technologies. Les avancées futures sont susceptibles d'introduire des méthodes encore plus optimisées, améliorant ainsi la vitesse et la précision des systèmes de récupération de données.