Analyse des méthodes de quantification des données

Tous les tests sont réalisés sur un ordi avec deux processeurs Intel Xeon Gold 6418H, tournant à 4,0GHz, avec 48 cœurs et 96 threads, et 1To de RAM. On utilise GCC 11.4.0 pour compiler le code source C++ sous Ubuntu 22.04 LTS. Pour nos méthodes, on évalue la performance en utilisant un thread pour la recherche, tandis qu'on mesure le temps d'indexation en utilisant plusieurs threads. Le code source est dispo en ligne.

On évalue la performance de différents algos avec six jeux de données publics qui mélangent dimensionnalité et types de données. Les spécificités de ces jeux de données sont présentées dans un tableau. Ces jeux incluent des benchmarks bien connus pour tester des algos comme ANN, ainsi que des embeddings produits par des modèles avancés d'OpenAI.

Pour les vecteurs de requête, on utilise soit le set fourni avec les jeux de données, soit on prend 1 000 vecteurs de chaque jeu pour la requête.

#Statistiques des Jeux de Données

Les stats des jeux de données sont les suivantes :

• MSong : Taille de 992 272, avec une taille de requête de 200 (Audio)
• Youtube : Taille de 999 000, avec une taille de requête de 1 000 (Vidéo)
• OpenAI-1536 : Taille de 999 000, avec une taille de requête de 1 000 (Texte)
• OpenAI-3072 : Taille de 999 000, avec une taille de requête de 1 000 (Texte)
• Word2Vec : Taille de 1 000 000, avec une taille de requête de 1 000 (Texte)
• GIST : Taille de 1 000 000, avec une taille de requête de 1 000 (Image)
• MSMARCO : Taille de 113 520 750, avec une taille de requête de 1 677 (Texte)

Dans nos expériences, on évalue l'équilibre entre l'espace utilisé et l'exactitude de l'estimation des distances, en évaluant plusieurs méthodes.

#Méthodes Évaluées

1. RaBitQ (ExT) : Une version étendue proposée dans cette étude.
2. RaBitQ (pad) : Une expansion basique de RaBitQ qui remplit les vecteurs avec des zéros.
3. SQ : Une méthode de quantification scalaire uniforme standard.
4. LVQ : Une variante plus récente de SQ qui utilise des plages de vecteurs individuelles pour la quantification.
5. PQ et OPQ : Des méthodes de quantification populaires utilisées avec des taux de compression élevés.

On insiste sur un taux de compression modéré, où le nombre de bits par dimension varie de 1 à 10. Pour des taux de compression plus élevés, l'exactitude diminue, tandis que des taux plus bas gaspillent de l'espace.

#Métriques de Performance

On mesure l'exactitude à travers l'erreur relative moyenne et l'erreur relative maximale dans les distances estimées. On mesure l'espace en utilisant le nombre de bits par dimension. Pour notre méthode, on prend aussi en compte l'espace nécessaire pour stocker deux nombres à virgule flottante pour chaque vecteur.

Dans le cadre des requêtes ANN, on applique des métriques de rappel et de ratio de distance moyenne pour évaluer l'exactitude. Le rappel montre le pourcentage de voisins les plus proches trouvés, tandis que le ratio de distance moyenne indique à quel point les vecteurs récupérés sont proches des vrais voisins les plus proches. On mesure aussi l'efficacité en requêtes par seconde (QPS).

#Résultats Expérimentaux

#Équilibre Espace-Exactitude pour l'Estimation de Distances

On regarde comment les différentes méthodes de quantification se débrouillent pour estimer les distances entre les données et les vecteurs de requête. En variant le nombre de bits utilisés, on trace des courbes illustrant les erreurs relatives moyennes et maximales de ces méthodes pour évaluer leur équilibre espace-exactitude.

D'après nos tests, on voit que la méthode RaBitQ étendue atteint constamment une meilleure précision que les autres sur les jeux de données pour le même nombre de bits. Par exemple, les méthodes traditionnelles comme LVQ et SQ montrent des erreurs relatives moyennes plus grandes. Ça suggère que notre méthode peut améliorer la performance en remplaçant ces anciennes méthodes.

#Équilibre Temps-Exactitude pour la Requête ANN

Ensuite, on explore comment les méthodes de quantification fonctionnent avec le système d'indexation IVF pour les requêtes ANN. On trace des courbes pour visualiser comment les requêtes par seconde se rapportent au rappel et au ratio de distance moyenne en variant le nombre de clusters utilisés.

Notre méthode montre un avantage significatif en efficacité, gérant plus de requêtes tout en maintenant l'exactitude. Notamment, avec une quantification de 4 bits, 5 bits et 7 bits, notre méthode atteint plus de 90 % de rappel sans besoin de re-ranker.

#Consommation d'Espace pour la Requête ANN

On compile la consommation d'espace des différentes méthodes pendant les requêtes ANN. Bien que notre méthode nécessite un peu plus d'espace que la baseline à cause du traitement par lots, c'est un petit sacrifice pour l'efficacité qu'elle offre.

#Temps de Quantification dans la Phase d'Indexation

On documente le temps requis pour quantifier les vecteurs de données dans la phase d'indexation en utilisant différents réglages. Les résultats indiquent que la quantification du dataset peut être effectuée dans un temps raisonnable, ce qui la rend pratique pour une utilisation réelle.

#Vérification de la Scalabilité

On étudie comment notre méthode se scale avec un large dataset d'environ 100 millions de vecteurs de données. Le temps nécessaire pour la quantification est d'environ deux heures, et on constate que notre méthode continue à offrir de meilleurs compromis temps-exactitude par rapport à LVQ.

#Vérification de l'Impartialité

Pour confirmer que notre nouveau codebook fournit des estimations impartiales, on collecte des paires de distances estimées et réelles. En ajustant ces paires à l'aide de la régression linéaire, on peut montrer que notre méthode estime correctement les distances.

#Mesure de la Formule Empirique

On mesure des constantes en rapport avec la relation entre les erreurs d'estimation pour les produits intérieurs. En échantillonnant des vecteurs unitaires et en appliquant notre méthode, on peut analyser comment les erreurs changent selon certains paramètres.

#Conclusion

Ce travail présente une analyse détaillée de différentes méthodes pour la quantification des données et la recherche ANN. Nos résultats montrent que la méthode RaBitQ étendue offre des améliorations notables en termes de précision et d'efficacité, surtout sous des taux de compression modérés. Les résultats soulignent l'importance du choix soigneux des paramètres pour atteindre les meilleures performances dans des applications réelles. La méthodologie décrite ici vise à faciliter des avancées supplémentaires dans le domaine du traitement des données et des systèmes de récupération.