Hashing es una operación central en la mayoría de las bases de datos en línea, como un catálogo de biblioteca o un sitio web de comercio electrónico. Una función hash genera códigos que determinan directamente la ubicación donde se almacenarían los datos. Entonces, usando estos códigos, es más fácil encontrar y recuperar los datos.
Sin embargo, debido a que las funciones hash tradicionales generan códigos aleatoriamente, a veces se pueden codificar dos datos con el mismo valor. Esto provoca colisiones: cuando la búsqueda de un elemento dirige al usuario a muchos datos con el mismo valor hash. Se tarda mucho más en encontrar el correcto, lo que da como resultado búsquedas más lentas y un rendimiento reducido.
Ciertos tipos de funciones hash, conocidas como funciones hash perfectas, están diseñadas para colocar los datos de manera que se eviten colisiones. Pero su construcción para cada conjunto de datos requiere mucho tiempo y lleva más tiempo calcular que las funciones hash tradicionales.
Dado que el hash se usa en tantas aplicaciones, desde la indexación de bases de datos hasta la compresión de datos y la criptografía, las funciones de hash rápidas y eficientes son críticas. Entonces, los investigadores del MIT y de otros lugares se propusieron ver si podían usar el aprendizaje automático para construir mejores funciones hash.
Descubrieron que, en ciertas situaciones, el uso de modelos aprendidos en lugar de funciones hash tradicionales podría generar la mitad de colisiones. Estos modelos aprendidos se crean ejecutando un algoritmo de aprendizaje automático en un conjunto de datos para capturar características específicas. Los experimentos del equipo también mostraron que los modelos aprendidos a menudo eran más eficientes computacionalmente que las funciones hash perfectas.
“Lo que encontramos en este trabajo es que, en algunas situaciones, podemos llegar a un mejor equilibrio entre el cálculo de la función hash y las colisiones que enfrentaremos. En estas situaciones, el tiempo de cálculo para la función hash se puede aumentar un poco, pero al mismo tiempo sus colisiones se pueden reducir de manera muy significativa”, dice Ibrahim Sabek, postdoctorado en el Grupo de Sistemas de Datos de Ciencias de la Computación e Inteligencia Artificial del MIT. Laboratorio (CSAIL).
Su investigación, que se presentará en la Conferencia Internacional sobre Bases de Datos Muy Grandes de 2023, demuestra cómo se puede diseñar una función hash para acelerar significativamente las búsquedas en una base de datos enorme. Por ejemplo, su técnica podría acelerar los sistemas informáticos que utilizan los científicos para almacenar y analizar ADN, secuencias de aminoácidos u otra información biológica.
Sabek es el coautor principal del artículo con el estudiante graduado del Departamento de Ingeniería Eléctrica y Ciencias de la Computación (EECS) Kapil Vaidya. A ellos se unen los coautores Dominick Horn, estudiante de posgrado en la Universidad Técnica de Munich; Andreas Kipf, un postdoctorado del MIT; Michael Mitzenmacher, profesor de informática en la Escuela de Ingeniería y Ciencias Aplicadas John A. Paulson de Harvard; y el autor principal Tim Kraska, profesor asociado de EECS en el MIT y codirector del Laboratorio de datos, sistemas e inteligencia artificial.
haciéndolo
Dada una entrada de datos, o clave, una función hash tradicional genera un número aleatorio, o código, que corresponde a la ranura donde se almacenará esa clave. Para usar un ejemplo simple, si hay 10 teclas para colocar en 10 ranuras, la función generaría un número entero aleatorio entre 1 y 10 para cada entrada. Es muy probable que dos llaves acaben en la misma ranura, provocando colisiones.
Las funciones hash perfectas proporcionan una alternativa sin colisiones. Los investigadores le dan a la función algunos conocimientos adicionales, como la cantidad de ranuras en las que se colocarán los datos. Luego puede realizar cálculos adicionales para averiguar dónde colocar cada tecla para evitar colisiones. Sin embargo, estos cálculos adicionales hacen que la función sea más difícil de crear y menos eficiente.
«Nos preguntábamos, si sabemos más sobre los datos, que provendrán de una distribución particular, ¿podemos usar modelos aprendidos para construir una función hash que realmente pueda reducir las colisiones?» Vaidya dice.
Una distribución de datos muestra todos los valores posibles en un conjunto de datos y con qué frecuencia ocurre cada valor. La distribución se puede usar para calcular la probabilidad de que un valor particular esté en una muestra de datos.
Los investigadores tomaron una pequeña muestra de un conjunto de datos y utilizaron el aprendizaje automático para aproximar la forma de la distribución de los datos, o cómo se distribuyen los datos. El modelo aprendido luego usa la aproximación para predecir la ubicación de una clave en el conjunto de datos.
Descubrieron que los modelos aprendidos eran más fáciles de construir y más rápidos de ejecutar que las funciones hash perfectas y que generaban menos colisiones que las funciones hash tradicionales si los datos se distribuyen de manera predecible. Pero si los datos no se distribuyen de manera predecible porque las brechas entre los puntos de datos varían demasiado, el uso de modelos aprendidos podría causar más colisiones.
“Es posible que tengamos una gran cantidad de entradas de datos, y las brechas entre las entradas consecutivas son muy diferentes, por lo que aprender un modelo para capturar la distribución de datos de estas entradas es bastante difícil”, explica Sabek.
Menos colisiones, resultados más rápidos
Cuando los datos se distribuían de forma predecible, los modelos aprendidos podían reducir la proporción de claves en conflicto en un conjunto de datos del 30 % al 15 %, en comparación con las funciones hash tradicionales. También pudieron lograr un mejor rendimiento que las funciones hash perfectas. En los mejores casos, los modelos aprendidos redujeron el tiempo de ejecución en casi un 30 por ciento.
A medida que exploraban el uso de modelos aprendidos para el hashing, los investigadores también descubrieron que el rendimiento se veía más afectado por la cantidad de submodelos. Cada modelo aprendido se compone de modelos lineales más pequeños que se aproximan a la distribución de datos para diferentes partes de los datos. Con más submodelos, el modelo aprendido produce una aproximación más precisa, pero lleva más tiempo.
“En un cierto umbral de submodelos, obtiene suficiente información para construir la aproximación que necesita para la función hash. Pero después de eso, no conducirá a más mejoras en la reducción de colisiones”, dice Sabek.
A partir de este análisis, los investigadores quieren utilizar modelos aprendidos para diseñar funciones hash para otros tipos de datos. También planean explorar el hashing aprendido para bases de datos en las que se pueden insertar o eliminar datos. Cuando los datos se actualizan de esta manera, el modelo debe cambiar en consecuencia, pero cambiar el modelo manteniendo la precisión es un problema difícil.
“Queremos alentar a la comunidad a utilizar el aprendizaje automático dentro de estructuras de datos y algoritmos más fundamentales. Cualquier tipo de estructura de datos central nos presenta la oportunidad de utilizar el aprendizaje automático para capturar las propiedades de los datos y obtener un mejor rendimiento. Todavía hay mucho que podemos explorar”, dice Sabek.
“Las funciones de hashing e indexación son fundamentales para muchas funciones de la base de datos. Dada la variedad de usuarios y casos de uso, no existe un hashing único para todos, y los modelos aprendidos ayudan a adaptar la base de datos a un usuario específico. Este documento es un gran análisis equilibrado de la viabilidad de estas nuevas técnicas y hace un buen trabajo al hablar rigurosamente sobre los pros y los contras, y nos ayuda a construir nuestra comprensión de cuándo se puede esperar que estos métodos funcionen bien”, dice Murali Narayanaswamy, un científico principal de aprendizaje automático en Amazon, que no participó en este trabajo. «Explorar este tipo de mejoras es un área emocionante de investigación tanto en la academia como en la industria, y el tipo de rigor que se muestra en este trabajo es fundamental para que estos métodos tengan un gran impacto».
Este trabajo fue apoyado, en parte, por Google, Intel, Microsoft, la Fundación Nacional de Ciencias de EE. UU., el Laboratorio de Investigación de la Fuerza Aérea de EE. UU. y el Acelerador de Inteligencia Artificial de la Fuerza Aérea de EE. UU.
