Simple Science

La science de pointe expliquée simplement

# Informatique# Bases de données# Structures de données et algorithmes# Recherche d'informations

Analyse des méthodes de quantification des données

Une étude sur la performance de différentes techniques de quantification des données pour une recherche efficace.

Jianyang Gao, Yutong Gou, Yuexuan Xu, Yongyi Yang, Cheng Long, Raymond Chi-Wing Wong

― 6 min lire


Aperçus sur laAperçus sur laquantification desdonnéesrecherche de données.efficacités dans les méthodes deUne étude révèle de nouvelles
Table des matières

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.

Source originale

Titre: Practical and Asymptotically Optimal Quantization of High-Dimensional Vectors in Euclidean Space for Approximate Nearest Neighbor Search

Résumé: Approximate nearest neighbor (ANN) query in high-dimensional Euclidean space is a key operator in database systems. For this query, quantization is a popular family of methods developed for compressing vectors and reducing memory consumption. Recently, a method called RaBitQ achieves the state-of-the-art performance among these methods. It produces better empirical performance in both accuracy and efficiency when using the same compression rate and provides rigorous theoretical guarantees. However, the method is only designed for compressing vectors at high compression rates (32x) and lacks support for achieving higher accuracy by using more space. In this paper, we introduce a new quantization method to address this limitation by extending RaBitQ. The new method inherits the theoretical guarantees of RaBitQ and achieves the asymptotic optimality in terms of the trade-off between space and error bounds as to be proven in this study. Additionally, we present efficient implementations of the method, enabling its application to ANN queries to reduce both space and time consumption. Extensive experiments on real-world datasets confirm that our method consistently outperforms the state-of-the-art baselines in both accuracy and efficiency when using the same amount of memory.

Auteurs: Jianyang Gao, Yutong Gou, Yuexuan Xu, Yongyi Yang, Cheng Long, Raymond Chi-Wing Wong

Dernière mise à jour: 2024-09-15 00:00:00

Langue: English

Source URL: https://arxiv.org/abs/2409.09913

Source PDF: https://arxiv.org/pdf/2409.09913

Licence: https://creativecommons.org/licenses/by-nc-sa/4.0/

Changements: Ce résumé a été créé avec l'aide de l'IA et peut contenir des inexactitudes. Pour obtenir des informations précises, veuillez vous référer aux documents sources originaux dont les liens figurent ici.

Merci à arxiv pour l'utilisation de son interopérabilité en libre accès.

Plus d'auteurs

Articles similaires