Científicos del MIT teorizan nuevo método para optimizar almacenamiento de datos

Investigadores del Instituto Tecnologico de Massachussets (MIT por sus siglas en inglés) encabezados por William Kuszmaul, han encontrado una forma de volver más eficaz el almacenamiento y recuperación de datos.

Este descubrimiento está basado en las conocidas tablas hash de sondeo lineal, este tipo de estructura brinda un nivel de organización más eficiente a nivel computacional.

Dichas tablas fueron introducidas en 1954 y se encuentran entre las estructuras de datos más antiguas, simples y rápidas disponibles en la actualidad.

Estas estructuras de datos proporcionan formas de organización y almacenamiento de datos en computadoras, lo que permite un resguardo de información largo de una matriz lineal.

“Suponiendo la fabricación de una base de datos para números de Seguridad Social de 10,000 personas, se toma su numero x, y calculamos la función hash de x, h (x). Esto proporciona un número aleatorio entre uno y 10,000, siguiente paso es tomar ese número aleatorio, ir a esa posición y poner el número de Seguro Social, en ese lugar” comentó Kuszmaul, quien también es estudiante del MIT.

De existir algún elemento en esa posición “simplemente avanza a la siguiente posición libre y se coloca allí, de aquí proviene el término sondeo lineal, avanza linealmente hasta encontrar un lugar abierto”.

Posteriormente, el almacenamiento de ese número es sencillo, el usuario deber ir a la posición asignada, en caso que no se encuentre en el lugar simplemente debe avanzar hasta encontrar el dato.

Si existiera la necesidad de eliminar algún elemento en la tabla, existe un protocolo diferente para quitarlo sin importar de qué se trate.

Si queda algún lugar vacío en la tabla hash posterior a la eliminación de la información, podría causar confusión en el sistema al intentar buscar otro elemento y sugerir erróneamente que el elemento no se encuentra en ninguna parte.

Para evitar ese problema, explica Kuszmaul, “puedes ir al lugar donde se eliminó el elemento y poner un pequeño marcador llamado ‘lápida’, indicando la previa existencia de un elemento en su lugar”.

Este procedimiento general se ha seguido durante más de medio siglo, desafortunadamente en este tiempo aquellos que hacen uso de las tablas hash de sondeo lineal han asumido que si permites un llenado excesivo, los tramos largos de lugares ocupados se juntarán en “grupos”.

Como resultado, el tiempo para encontrar un lugar libre aumentaría drásticamente, generando un sistema menos efectivo e impráctico.

En consecuencia y con la finalidad de eliminar este problema, Kuszmaul y su equipo descubrieron una nueva estrategia llamada “hash de cementerio”, que implica aumentar artificialmente el número de lápidas colocadas en una matriz hasta ocupar la mitad de los lugares libres.

Estas lápidas reservan espacios que se pueden utilizar para futuras inserciones, “puede conducir a un rendimiento óptimo en tablas hash de sondeo lineal”, dice Kuszmaul.

El profesor de informática del MIT Charles E. Leiserson agregó; “Estos resultados nuevos y sorprendentes anulan una de las creencias convencionales más antiguas sobre el comportamiento de la tabla hash”. Por otro lado, los investigadores destacaron que pese al avance teórico, apenas se comienza a explorar el lado experimental de dichas formas de organización, a fin de mejorar el almacenamiento y recuperación de datos.

NotiPress/Ricardo Cocoletzi

Soy el mero mero que le pone sabor a tus chilaquiles, el tamal de tu torta, la pasta de tu cepillo de dientes, la machaca de tu huevo, soy el gaio y cuando canto sale pura neta.
Lo que quiero decir es que soy la voz oficial de este lugar y espero lean mis palabras. Informo de todo un poco. Queremos verte diario por aquí.