Alfredo Viola: Una visión unificada del análisis de linear probing hashing

Palabras Claves: hashing; linear probing; buckets; funciones generatrices; Combinatoria Analítica

Resumen:

 En 1998, Knuth motivó su importante trabajo "Linear Probing and Graphs" de la siguiente manera:

 "El propósito de esta nota es presentar una solución sorprendentemente simple a un problema que apareció en un libro reciente de Sedgweick y Flajolet:

Exercise 8.39: Usar el método simbólico para derivar funciones generatrices exponenciales del número de pruebas necesarias en línear probing hashing para realizar una búsqueda exitosa, para M fijo".

Por otro lado, al final de dicho paper en sus comentarios personales declara: "ninguno de los métodos disponibles en 1962 (cuandó
realizó el primer análisis de linear probing y que es considerado el origen del área de análisis de algoritmos) era suficientemente poderoso para calcular el valor esperado del desplazamiento cuadrático, y mucho menos para cualcular momentos de orden superior. Por tal motivo, es un placer muy grande el poder haber derivado estos resultados al día de hoy basado en el trabajo de metodología fundamental que ha enriquecido el área de combinatoria durante los últimos 35 años".

En este sentido, se está refiriendo al desarrollo del área de Combinatoria Analítica y que se resume en el libro fundamental del
área, "Analytic Combinatorics" presentado en 2009 por Flajolet y Sedgewick.

En esta charla presento recientes resultados desarrollados en conjunto con Svante Janson (Uppsala University, Suecia) en donde
presentamos de una manera unificada el análisis distribucional de varias variables aleatorias relacionados con linear probing hashing con cubetas de tamaño b constante. Presentamos de una manera explícita y exacta funciones generatrices trivariadas en el modelo combinatorio junto con funciones generatrices bivariadas en el modelo de Poisson.
Presentamos también como conectar los resultados en los diferentes modelos.

El análisis en el modelo asimptótico de Poisson se fundamenta en la relación profunda entre caminos aleatorios ("random walks") y linear probing. Por otro lado, la derivación de los resultados en el modelo combinatorio están basados en el uso del método simbólico para especificar el problema y su traducción directa en funciones generatrices exponenciales (tal cual lo pedido en la cita referenciada en el trabajo de Knuth de 1998). Es la primera presentación unificada del análisis del algoritmo de linear probing hashing usando todo el poder de las herramientas desarrolladas por la Combinatoria Analítica, donde llevamos a la práctica el legado fundamental de Philippe Flajolet ("si lo puedes especificar lo puedes analizar").

Las herramientas fundamentales para usar el método simbólico fueron tomadas de una presentación de Philippe Flajolet de 1998, con ideas que no han sido publicadas. En este sentido se presenta la traducción entre la especificación de estos problemas y q-análogos de sus correspondientes funciones generatrices.

En esta charla presentaré los fundamentos del algoritmo, los fundamentos matemáticos para analizar estos algoritmos y las nuevas
contribuciones. Es apta para público general, dada la elegancia y potencia de los métodos basados en combinatoria analítica. Presentaré también las ideas fundamentales del modelo de Poisson y la relación entre ambos modelos.