Une nouvelle méthode pour booster la vitesse des bases de données en ligne

Le hachage est une opération centrale dans la plupart des bases de données en ligne, comme un catalogue de bibliothèque ou un site Web de commerce électronique. Une fonction de hachage génère des codes qui remplacent les entrées de données. Étant donné que ces codes sont plus courts que les données réelles et généralement de longueur fixe, cela facilite la recherche et la récupération des informations d’origine.

Cependant, étant donné que les fonctions de hachage traditionnelles génèrent des codes de manière aléatoire, il est parfois possible de hacher deux données avec la même valeur. Cela provoque des collisions – lorsque la recherche d’un élément pointe un utilisateur vers plusieurs éléments de données avec la même valeur de hachage. Il faut beaucoup plus de temps pour trouver le bon, ce qui ralentit les recherches et réduit les performances.

Certains types de fonctions de hachage, appelées fonctions de hachage parfaites, sont conçues pour trier les données de manière à éviter les collisions. Mais elles doivent être spécialement construites pour chaque ensemble de données et prendre plus de temps à calculer que les fonctions de hachage traditionnelles.

Étant donné que le hachage est utilisé dans de nombreuses applications, de l’indexation des bases de données à la compression des données en passant par la cryptographie, des fonctions de hachage rapides et efficaces sont essentielles. Ainsi, des chercheurs du MIT et d’ailleurs ont cherché à savoir s’ils pouvaient utiliser l’apprentissage automatique pour créer de meilleures fonctions de hachage.

Ils ont constaté que, dans certaines situations, l’utilisation de modèles appris au lieu de fonctions de hachage traditionnelles pouvait entraîner deux fois moins de collisions. Les modèles appris sont ceux qui ont été créés en exécutant un algorithme d’apprentissage automatique sur un ensemble de données. Leurs expériences ont également montré que les modèles appris étaient souvent plus efficaces en termes de calcul que les fonctions de hachage parfaites.

“Ce que nous avons trouvé dans ce travail, c’est que dans certaines situations, nous pouvons trouver un meilleur compromis entre le calcul de la fonction de hachage et les collisions auxquelles nous serons confrontés. Nous pouvons augmenter un peu le temps de calcul de la fonction de hachage, mais au En même temps, nous pouvons réduire les collisions de manière très significative dans certaines situations », explique Ibrahim Sabek, post-doctorant au sein du MIT Data Systems Group du Laboratoire d’informatique et d’intelligence artificielle (CSAIL).

Leur recherche, qui sera présentée à la Conférence internationale sur les très grandes bases de données, démontre comment une fonction de hachage peut être conçue pour accélérer considérablement les recherches dans une énorme base de données. Par exemple, leur technique pourrait accélérer les systèmes informatiques que les scientifiques utilisent pour stocker et analyser l’ADN, les séquences d’acides aminés ou d’autres informations biologiques.

Sabek est co-auteur principal de l’article avec l’étudiant diplômé en génie électrique et informatique (EECS) Kapil Vaidya. Ils sont rejoints par les co-auteurs Dominick Horn, étudiant diplômé de l’Université technique de Munich ; Andreas Kipf, postdoctorant au MIT ; Michael Mitzenmacher, professeur d’informatique à la Harvard John A. Paulson School of Engineering and Applied Sciences ; et l’auteur principal Tim Kraska, professeur agrégé d’EECS au MIT et codirecteur du Data Systems and AI Lab.

Le hacher

Étant donné une entrée de données, ou clé, une fonction de hachage traditionnelle génère un nombre aléatoire, ou code, qui correspond à l’emplacement où cette clé sera stockée. Pour utiliser un exemple simple, s’il y a 10 clés à mettre dans 10 emplacements, la fonction générerait un entier aléatoire entre 1 et 10 pour chaque entrée. Il est fort probable que deux clés se retrouvent dans le même emplacement, provoquant des collisions.

Les fonctions de hachage parfaites offrent une alternative sans collision. Les chercheurs donnent à la fonction des connaissances supplémentaires, telles que le nombre d’emplacements dans lesquels les données doivent être placées. Ensuite, il peut effectuer des calculs supplémentaires pour déterminer où placer chaque clé pour éviter les collisions. Cependant, ces calculs supplémentaires rendent la fonction plus difficile à créer et moins efficace.

“Nous nous demandions si nous en savions plus sur les données – qu’elles proviendraient d’une distribution particulière – pourrions-nous utiliser des modèles appris pour créer une fonction de hachage qui puisse réellement réduire les collisions ?” dit Vaidya.

Une distribution de données affiche toutes les valeurs possibles dans un jeu de données et la fréquence à laquelle chaque valeur se produit. La distribution peut être utilisée pour calculer la probabilité qu’une valeur particulière se trouve dans un échantillon de données.

Les chercheurs ont pris un petit échantillon d’un ensemble de données et ont utilisé l’apprentissage automatique pour approximer la forme de la distribution des données, ou la façon dont les données sont réparties. Le modèle appris utilise ensuite l’approximation pour prédire l’emplacement d’une clé dans l’ensemble de données.

Ils ont constaté que les modèles appris étaient plus faciles à construire et plus rapides à exécuter que les fonctions de hachage parfaites et qu’ils entraînaient moins de collisions que les fonctions de hachage traditionnelles si les données étaient distribuées de manière prévisible. Mais si les données ne sont pas distribuées de manière prévisible, car les écarts entre les points de données varient trop largement, l’utilisation de modèles appris peut entraîner davantage de collisions.

“Nous pouvons avoir un grand nombre d’entrées de données, et chacune a un écart différent entre elle et la suivante, donc apprendre cela est assez difficile”, explique Sabek.

Moins de collisions, des résultats plus rapides

Lorsque les données étaient distribuées de manière prévisible, les modèles appris pouvaient réduire le taux de collisions de clés dans un ensemble de données de 30 % à 15 %, par rapport aux fonctions de hachage traditionnelles. Ils ont également pu obtenir un meilleur débit que les fonctions de hachage parfaites. Dans le meilleur des cas, les modèles appris ont réduit le temps d’exécution de près de 30 %.

En explorant l’utilisation de modèles appris pour le hachage, les chercheurs ont également découvert que tout était le plus impacté par le nombre de sous-modèles. Chaque modèle appris est composé de modèles linéaires plus petits qui se rapprochent de la distribution des données. Avec plus de sous-modèles, le modèle appris produit une approximation plus précise, mais cela prend plus de temps.

“À un certain seuil de sous-modèles, vous obtenez suffisamment d’informations pour construire l’approximation dont vous avez besoin pour la fonction de hachage. Mais après cela, cela n’améliorera pas davantage la réduction des collisions”, déclare Sabek.

S’appuyant sur cette analyse, les chercheurs souhaitent utiliser des modèles appris pour concevoir des fonctions de hachage pour d’autres types de données. Ils prévoient également d’explorer le hachage appris pour les bases de données dans lesquelles des données peuvent être insérées ou supprimées. Lorsque les données sont mises à jour de cette manière, le modèle doit changer en conséquence, mais changer le modèle tout en maintenant la précision est un problème difficile.

“Nous voulons encourager la communauté à utiliser l’apprentissage automatique dans des structures de données et des opérations plus fondamentales. Tout type de structure de données de base nous offre une opportunité d’utiliser l’apprentissage automatique pour capturer les propriétés des données et obtenir de meilleures performances. Nous pouvons encore explorer beaucoup de choses. “, dit Sabek.

Cette histoire est republiée avec l’aimable autorisation de MIT News (web.mit.edu/newsoffice/), un site populaire qui couvre l’actualité de la recherche, de l’innovation et de l’enseignement du MIT.