ACORN : Une nouvelle approche de la recherche hybride

Dans le monde d'aujourd'hui, les données existent sous plein de formes, comme des images, du texte, des vidéos et des données structurées, genre des chiffres et des mots-clés. Les entreprises et les chercheurs ont souvent besoin de chercher et de trouver des infos pertinentes parmi ces types de données mélangées. Cependant, les méthodes actuelles pour fouiller dans ces types variés galèrent souvent. Soit elles ne fonctionnent pas bien, soit elles ne permettent que des recherches simples, ce qui complique leur utilisation.

Pour résoudre ce problème, on vous présente une nouvelle méthode appelée ACORN. Cette méthode permet une recherche rapide et flexible à travers un mélange de données vectorielles (comme des images et du texte) et de données structurées (comme des chiffres et des mots-clés). ACORN est conçu pour être efficace et peut gérer une grande variété de Requêtes de recherche, ce qui le rend pratique pour des applications concrètes.

#Le défi des données mixtes

Beaucoup d'applications ont besoin de chercher à travers différents types de données en même temps. Par exemple, quelqu'un qui fait du shopping en ligne voudrait peut-être trouver des t-shirts similaires à partir d'une image de référence tout en filtrant les résultats par prix. De même, des chercheurs voudraient trouver des articles en utilisant des requêtes en langage naturel avec des filtres basés sur des mots-clés ou des dates de publication.

Pour rendre cela possible, les systèmes de gestion de données doivent supporter des requêtes de recherche hybrides qui combinent la recherche de similarité avec des filtres structurés. Cela nécessite deux choses principales :

1. Performance : Le système doit trouver rapidement et avec précision les résultats, même quand la charge de recherche varie.
2. Flexibilité : Le système doit supporter une large gamme de types de requêtes que les utilisateurs pourraient saisir, comme des mots-clés ou des plages de chiffres spécifiques.

Cependant, les systèmes existants peinent souvent à répondre à ces exigences. Ils utilisent généralement l'une des trois stratégies : pré-filtrage, post-filtrage ou des structures de données spécialisées conçues pour des requêtes simples.

#Pré-Filtrage

Dans le pré-filtrage, le système trouve d'abord tous les enregistrements qui répondent à la requête structurée, puis effectue une recherche de similarité sur le petit ensemble de résultats. Bien que cela puisse garantir une haute précision, ça devient inefficace avec des ensembles de données plus grands et des requêtes complexes, car la performance chute à mesure que le nombre d'enregistrements augmente.

#Post-Filtrage

Le post-filtrage fonctionne à l'opposée. Il commence par effectuer une recherche de similarité sur l'ensemble du jeu de données, puis enlève les enregistrements qui ne répondent pas aux critères de la requête structurée. Cette méthode peut entraîner des efforts gaspillés puisque le système pourrait chercher à travers des résultats qu'il finirait par écarter.

#Systèmes Spécialisés

Certains systèmes plus récents utilisent des méthodes spécialisées qui sont conçues pour des recherches simples. Par exemple, certaines méthodes ne peuvent gérer qu'un nombre limité d'attributs structurés ou de types de requêtes. Ça peut les rendre moins utiles pour des applications du monde réel qui nécessitent de la flexibilité.

#Présentation d'ACORN

ACORN signifie Réseau de Récupération Optimisé par Contraintes ANN. Il aborde les limites des méthodes existantes et permet des recherches mixtes qui peuvent gérer divers types de requêtes. ACORN s'appuie sur une méthode appelée HNSW (Hierarchical Navigable Small Worlds), qui est reconnue comme l'une des meilleures méthodes pour les données de haute dimension.

#Comment ACORN fonctionne

ACORN modifie la structure HNSW pour permettre des recherches rapides sur un ensemble plus large de types de requêtes. L'une de ses caractéristiques clés est le concept de parcours de sous-graphe prédicatif. Cela signifie que durant une recherche, ACORN navigue à travers une partie spécifique de l'index, se concentrant uniquement sur les données qui passent une condition de recherche donnée. Cela lui permet de fonctionner efficacement même lorsqu'il y a beaucoup de filtres potentiels et de requêtes complexes.

#Design Indépendant du Prédicat

La stratégie de recherche d'ACORN est conçue pour être flexible. Elle ne dépend pas de la connaissance de tous les types de requêtes possibles à l'avance. Au lieu de cela, elle construit son index de manière à pouvoir gérer automatiquement de nombreux filtres et types de recherches différents. Cela signifie qu'elle peut bien fonctionner peu importe les requêtes spécifiques que les utilisateurs saisissent.

#Évaluation d'ACORN

Pour s'assurer qu'ACORN fonctionne bien, nous avons effectué des tests sur différents ensembles de données. Nous avons examiné à la fois des benchmarks traditionnels, qui impliquent des requêtes structurées simples, ainsi que des ensembles de données plus récents qui utilisent des requêtes plus complexes avec de nombreuses variables.

#Aperçu des Résultats

Dans nos évaluations, ACORN a systématiquement surpassé les méthodes existantes, atteignant un nombre de requêtes par seconde (QPS) plus élevé tout en maintenant une grande précision. Plus précisément, il a montré des améliorations de 2 à 1 000 fois en performance, en fonction de l'ensemble de données et du type de requête.

#Descriptions des Ensembles de Données

Nous avons testé ACORN sur une variété d'ensembles de données pour évaluer sa performance à travers différents types de données. Voici un bref aperçu de ces ensembles de données :

1. SIFT1M : Un ensemble de données avec 1 million de vecteurs d'images et 10 000 requêtes.
2. Paper : Un ensemble de données contenant 2 millions de vecteurs dérivés d'articles académiques.
3. TripClick : Implique des requêtes réelles d'un moteur de recherche web santé, contenant de nombreux attributs structurés.
4. LAION : Un grand ensemble de données d'embeddings d'images et leurs descriptions textuelles correspondantes.

Ces ensembles de données ont aidé à illustrer l'efficacité d'ACORN dans des scénarios de requêtage simples et complexes.

#Analyse de Performance

Nous avons examiné à quel point ACORN pouvait récupérer des résultats pertinents face à différents types de requêtes et de sélectivités.

#Requêtes de Basse Cardinalité vs. Haute Cardinalité

Dans les ensembles de données avec des ensembles de prédicats de basse cardinalité, ce qui signifie qu'il y a seulement quelques filtres de requête structurée possibles, ACORN a montré des gains substantiels par rapport aux méthodes existantes. Il a maintenu son efficacité tout en atteignant une haute précision dans les résultats.

D'un autre côté, dans les ensembles de données avec des ensembles de prédicats de haute cardinalité (beaucoup de filtres possibles), ACORN a toujours surpassé toutes les autres méthodes. Ceci est significatif car de nombreux scénarios du monde réel impliquent des requêtes complexes qui ne peuvent pas être facilement gérées avec les systèmes précédents.

#Corrélation des Requêtes

Nous avons aussi analysé comment ACORN gérait différents types de corrélation des requêtes :

• Corrélation positive : Lorsque la requête et les résultats pertinents sont étroitement liés.
• Corrélation négative : Où il y a des divergences entre la requête et les résultats possibles.
• Aucune corrélation : Lorsque la requête n'est pas bien liée aux résultats.

Le design d'ACORN lui a permis d'exceller avec différents degrés de corrélation, dépassant les systèmes de référence dans tous les scénarios.

#Efficacité de Construction

En plus de la performance de recherche, nous avons évalué comment ACORN gérait la construction de l'index. Construire l'index de manière efficace est crucial pour des applications pratiques.

#Temps de Construction de l'Index (TTI)

Nous avons mesuré combien de temps il a fallu pour construire l'index ACORN. Son temps de construction a été trouvé relativement rapide par rapport à d'autres méthodes, garantissant qu'il puisse être déployé avec un délai minimal dans des applications réelles.

ACORN-1, une variante d'ACORN, a même atteint des temps de construction encore plus rapides tout en maintenant un niveau raisonnable de performance de recherche.

#Taille de l'Index

La taille de l'index est aussi un facteur critique. Étant donné qu'ACORN est conçu pour être efficace, il a maintenu une taille d'index plus petite comparée à de nombreux systèmes existants. Cette taille réduite signifie qu'il nécessite moins de stockage et peut être plus facilement géré et évolué.

#Conclusion

ACORN représente une avancée significative dans les capacités de recherche hybride, permettant aux utilisateurs de naviguer efficacement à travers les données vectorielles et structurées. Son design flexible le rend adapté à une large gamme d'applications, du e-commerce à la recherche académique.

En naviguant efficacement à travers les défis des formats de données mixtes, en atteignant une performance supérieure à travers les ensembles de données, et en garantissant des temps de construction rapides, ACORN se présente comme une solution pratique pour les problèmes modernes de récupération d'informations.

Il est clair d'après nos évaluations qu'ACORN établit une nouvelle norme dans les systèmes de recherche hybride, promettant d'améliorer les capacités des applications basées sur les données à l'avenir.