Estudiante DCC obtiene Premio Capocelli

Image preview

Héctor Ferrada fue destacado en Data Compression Conference 2016, realizada en Snowbird, Estados Unidos.


Compartir

Héctor Ferrada fue destacado en Data Compression Conference 2016, realizada en Snowbird, Estados Unidos.

 

"Improved Range Minimum Queries" es el título del paper que obtuvo el Premio Capocelli en la Conferencia Data Compression, realizada en Snowbird, Estados Unidos y que fue escrito por Héctor Ferrada, alumno de Doctorado del Departamento de Ciencias de la Computación, y Gonzalo Navarro, académico del mismo.

 

El galardón se entrega al mejor paper escrito por un estudiante, considerando la opinión de los revisores del paper y del comité de programa luego de ver la presentación del estudiante.

 

Este año el premio fue compartido entre dos papers. El paper de Ferrada y Navarro fue destacado por entregar una solución al problema de calcular Range Minimum Queries (RMQs).

 

“Me siento muy feliz de recibir este premio, por lo cual doy gracias primeramente a Dios, a esta gran casa de estudios y a la notable labor de mi supervisor, Gonzalo Navarro. Siento que esto es el resultado de nuestro esfuerzo y trabajo constante", afirma Héctor.

 

"Esta propuesta nació el año 2013, donde construimos nuestra primera versión con paréntesis balanceados, ya que necesitábamos una estructura que responda RMQs para incluir en nuestro índice LZ-DL (Ferrada y Navarro SPIRE-2013) y no había en la comunidad una buena implementación disponible. Sin embargo obtuvimos una implementación que no era tan rápida como la actual, ya que aún teníamos una fórmula compleja”, señala el estudiante.

 

Aportes a la disciplina

 

“En la práctica esta solución es más eficiente (en términos de tiempo y espacio), y en la teoría es más elegante. Es de esperar que, de aquí en adelante, quien necesite una implementación de RMQs use la nuestra”, agrega Gonzalo Navarro.

 

“El problema de RMQs es preprocesar un arreglo de números A[1,n] para luego responder preguntas del tipo: ¿Dónde aparece el mínimo valor en A[i,j]? Este es un problema con una larga tradición algorítmica. Surgió relacionado con el problema de Lowest Common Ancestors (LCAs) en árboles, que busca, en un árbol, el nodo más bajo que es ancestro de dos nodos dados. Este problema fue definido por Aho, Hopcroft y Ullman en 1973, y la primera solución de tiempo constante es recién de 1984, por Harel y Tarjan. En 1984 Gabow relacionó el problema con las RMQs (mostrando que RMQs se resuelven usando LCAs sobre los arboles cartesianos de Vuillemin de 1980) y en 1993 Berkman y Vishkin mostraron la relación inversa (mostrando que LCAs se resuelven usando RMQs). Las soluciones actuales a RMQs se basan en los trabajos de Bender y Farach (2000), Fischer y Heun (2011) y Navarro y Sadakane (2014). Nuestra contribución fue simplificar y mejorar el esquema de Fischer y Heun, además de usar una buena implementación de Navarro y Sadakane”, señala el académico y agrega: “El problema de RMQ/LCA es fundamental y aparece como subproblema de otros más aplicados, por ejemplo: búsqueda en texto permitiendo errores, búsqueda de patrones complejos usando arboles de sufijos, recuperación de información en colecciones genéricas de secuencias, implementación de lenguajes orientados a objetos, modelación de sistemas complejos, computación distribuida, problemas en geometría computacional y en recorridos de grafos”.

 

En esta misma línea Héctor sostiene: “La primera gran contribución de nuestra propuesta es brindar una variante que asegura las mismas garantías asintóticas que la mejor solución existente hasta hoy (Fischer y Heun SIAM-2011) pero simplificando el cómputo de la respuesta. En el paper mostramos que mediante una representación con paréntesis balanceados para el árbol introducido por Fischer & Heun, que se construye sobre el arreglo de entrada, el cálculo de la respuesta resulta mucho más sencillo ya que no es necesario validar ningún tipo de condiciones de borde. Esto nos evita verificar, por ejemplo, si un nodo es ancestro de otro, cálculo que sí debe hacer la otra propuesta, ahorrándonos una costosa operación en términos de tiempo”, afirma.

 

Y añade: “En segundo lugar ofrecemos, en términos de espacio utilizado y tiempo de cómputo, la mejor implementación que hoy existe a este problema. Nuestra estructura requiere alrededor de 2.2n bits de espacio en memoria. Esto lo hemos logrado al utilizar una representación simplificada del Range Min-Max Tree (RMMT) (Navarro y Sadakane ACM TALG-2014). Así, para el RMMT, y gracias al reducido número de operaciones de nuestra fórmula, solo necesitamos almacenar valores mínimos de rangos y no todos los valores de una implementación completa del RMMT. Todo esto ha dado como resultado una implementación (en 64 bits) que no solamente es muy compacta, sino que también es muy rápida, la cual responde consultas RMQs entre 1 y 4 microsegundos”, finaliza Ferrada.