Une percée théorique pourrait stimuler le stockage de données

stockage de données

Crédit : Pixabay/CC0 domaine public

Un trio de chercheurs qui comprend William Kuszmaul, un docteur en informatique. étudiant au MIT – a fait une découverte qui pourrait conduire à un stockage et une récupération de données plus efficaces dans les ordinateurs.

Les découvertes de l’équipe concernent les “tables de hachage à sondage linéaire”, qui ont été introduites en 1954 et sont parmi les structures de données les plus anciennes, les plus simples et les plus rapides disponibles aujourd’hui. Les structures de données fournissent des moyens d’organiser et de stocker des données dans des ordinateurs, les tables de hachage étant l’une des approches les plus couramment utilisées. Dans une table de hachage à sondage linéaire, les positions dans lesquelles les informations peuvent être stockées se trouvent le long d’un réseau linéaire.

Supposons, par exemple, qu’une base de données soit conçue pour stocker les numéros de sécurité sociale de 10 000 personnes, suggère Kuszmaul. « Nous prenons votre numéro de sécurité sociale, x, et nous calculerons ensuite la fonction de hachage de x, h(x), qui vous donne un nombre aléatoire compris entre un et 10 000 ». L’étape suivante consiste à prendre ce nombre aléatoire, h(x), à aller à cette position dans le tableau et à mettre x, le numéro de sécurité sociale, à cet endroit.

S’il y a déjà quelque chose qui occupe cet endroit, dit Kuszmaul, “vous avancez simplement vers la prochaine position libre et mettez-le là. C’est de là que vient le terme” sondage linéaire “, alors que vous continuez à avancer linéairement jusqu’à ce que vous trouviez un endroit libre. .” Afin de récupérer plus tard ce numéro de sécurité sociale, x, vous allez simplement à l’endroit désigné, h(x), et s’il n’y est pas, vous avancez jusqu’à ce que vous trouviez x ou arriviez à une position libre et concluez que x est pas dans votre base de données.

Il existe un protocole quelque peu différent pour supprimer un élément, tel qu’un numéro de sécurité sociale. Si vous venez de laisser un espace vide dans la table de hachage après avoir supprimé les informations, cela pourrait causer de la confusion lorsque vous essaierez plus tard de trouver autre chose, car l’emplacement vacant pourrait suggérer à tort que l’élément que vous recherchez est introuvable dans la base de données. Pour éviter ce problème, explique Kuszmaul, “vous pouvez vous rendre à l’endroit où l’élément a été supprimé et y mettre un petit marqueur appelé” pierre tombale “, qui indique qu’il y avait un élément ici, mais qu’il a disparu maintenant. “

Cette procédure générale est suivie depuis plus d’un demi-siècle. Mais pendant tout ce temps, presque tout le monde utilisant des tables de hachage à sondage linéaire a supposé que si vous leur permettez d’être trop pleins, de longues étendues de points occupés se regrouperaient pour former des “clusters”. En conséquence, le temps qu’il faudrait pour trouver une place libre augmenterait considérablement – ​​de manière quadratique, en fait – prenant tellement de temps qu’il serait impraticable. Par conséquent, les gens ont été formés pour utiliser des tables de hachage à faible capacité, une pratique qui peut coûter cher en affectant la quantité de matériel qu’une entreprise doit acheter et entretenir.

Mais ce principe séculaire, qui a longtemps milité contre des facteurs de charge élevés, a été totalement bouleversé par les travaux de Kuszmaul et de ses collègues, Michael Bender de l’université Stony Brook et Bradley Kuszmaul de Google. Ils ont découvert que pour les applications où le nombre d’insertions et de suppressions reste à peu près le même et la quantité de données ajoutées est à peu près égale à celle supprimée, les tables de hachage à sondage linéaire peuvent fonctionner à des capacités de stockage élevées sans sacrifier la vitesse.

En outre, l’équipe a mis au point une nouvelle stratégie, appelée « hachage de cimetière », qui consiste à augmenter artificiellement le nombre de pierres tombales placées dans un réseau jusqu’à ce qu’elles occupent environ la moitié des emplacements libres. Ces pierres tombales réservent alors des espaces qui peuvent être utilisés pour de futures insertions.

Cette approche, qui va à l’encontre de ce que les gens ont l’habitude de faire, dit Kuszmaul, “peut conduire à des performances optimales dans les tables de hachage à sondage linéaire”. Ou, comme lui et ses coauteurs le maintiennent dans leur article, « l’utilisation bien conçue des pierres tombales peut complètement changer le… paysage du comportement du sondage linéaire ».

Kuszmaul a rédigé ces découvertes avec Bender et Kuszmaul dans un article publié plus tôt cette année qui sera présenté en février au Symposium Foundations of Computer Science (FOCS) à Boulder, Colorado.

Le doctorat de Kuszmaul. Le directeur de thèse, le professeur d’informatique du MIT Charles E. Leiserson (qui n’a pas participé à cette recherche), est d’accord avec cette évaluation. “Ces résultats nouveaux et surprenants renversent l’une des plus anciennes idées reçues sur le comportement des tables de hachage”, déclare Leiserson. “Les leçons se répercuteront pendant des années parmi les théoriciens et les praticiens.”

Quant à la traduction de leurs résultats dans la pratique, note Kuszmaul, « il y a de nombreuses considérations à prendre en compte dans la construction d’une table de hachage. Bien que nous ayons considérablement avancé l’histoire d’un point de vue théorique, nous commençons tout juste à explorer le côté expérimental des choses. ”


La nouvelle structure de données permet un suivi et un contrôle rapides des données du réseau


Plus d’information:
Sondage linéaire revisité : les pierres tombales marquent la mort du clustering principal, arXiv : 2107.01250 [cs.DS] arxiv.org/abs/2107.01250

Fourni par le Massachusetts Institute of Technology

Citation: Une percée théorique pourrait augmenter le stockage de données (2021, 16 novembre) récupéré le 16 novembre 2021 à partir de https://techxplore.com/news/2021-11-theoretical-breakthrough-boost-storage.html

Ce document est soumis au droit d’auteur. En dehors de toute utilisation équitable à des fins d’étude ou de recherche privée, aucune partie ne peut être reproduite sans l’autorisation écrite. Le contenu est fourni seulement pour information.