Cuatro estudiantes del Magíster en Informática (MIN) de la Universidad Austral de Chile fueron seleccionados para presentar sus artículos de investigación en las Jornadas Chilenas de Computación, evento científico más importante que se organiza y realiza en el país en el ámbito de la ciencia de la computación y de la informática, siendo reconocido por las dos más importantes sociedades científicas mundiales en su ámbito: la ACM y la IEEE.
El evento se lleva a cabo entre el 21 y 25 de noviembre en Santiago y con transmisión en línea, permitiendo la participación de expositores nacionales e internacionales.
Benjamín Letelier, Enzo Meneses y Rodrigo Stevenson fueron seleccionados para la exposición de artículos producto de sus trabajos de tesis, mientras que Sebastián Pacheco participa con un artículo en el Encuentro de Tesistas. También fue seleccionado el artículo de Alan Keith, egresado del MIN.
Los académicos del MIN Cristóbal Navarro y Héctor Ferrada, patrocinantes de los proyectos de investigación de los estudiantes de postgrado, destacaron que este grupo de jóvenes haya sido seleccionado para participar en este evento científico, resaltando que además de ir a presentar publican un artículo que queda en la IEEE Xplore (Scopus).
“Lo más destacable es que todos los trabajos de la UACh fueron aceptados luego de haber pasado por un proceso de revisión de pares (peer review) de forma análoga a la publicación en un journal. Si consideramos que sólo alrededor del 35% de los trabajos enviados fueron aceptados, es un indicador de que las investigaciones que están desarrollando nuestros estudiantes desde el sur de Chile son relevantes y novedosas para el estado del arte en computación. El beneficio académico es que contarán con una publicación IEEE Xplore (Scopus) en su currículum donde ellos van como primer autor, algo muy importante tanto para postular a un futuro doctorado en cualquier lugar del mundo o a un trabajo importante en la industria. Otro beneficio es que con asistir a estas conferencias ellos comienzan a construir-fortalecer sus redes de colaboración nacional e internacional”, señaló Cristóbal Navarro.
Artículos de investigación
Benjamín Letelier Lazo, en coautoría con el Dr. Héctor Ferrada, presentará el artículo «A CPU-Parallel Implementation of Pattern Matching for the Hybrid Index«. Este trabajo describe que Pattern Matching (PM) es uno de los problemas principales en el análisis de texto y se puede definir como encontrar todas las ocurrencias de un patrón P en un texto T. Este problema es resuelto a diario por todas las personas, como cuando buscamos una palabra en un PDF o hacemos una consulta en Google. A medida que los tiempos avanzan, la cantidad de información a buscar es mayor, por lo que las técnicas algorítmicas que dependen del tamaño del T tienden a quedar obsoletas.
Para remediar esto, existe un auge en técnicas comprimidas que permiten resolver PM con tiempos muy buenos, pero ocupando una cantidad de espacio mucho menor que el texto original, permitiendo trabajar con los grandes volúmenes de información que existen en la actualidad. El Hybrid Index (HI) es la solución comprimida que menos espacio ocupa en la
actualidad y posee tiempos muy buenos para resolver PM en todo tipo de texto, además de un algoritmo de PM altamente paralelizable. Este trabajo mejora considerablemente los tiempos del HI a través de la paralelización en CPU de su algoritmo que resuelve PM tanto en textos repetitivos como no repetitivos.
El segundo artículo de investigación corresponde al estudiante Enzo Meneses, en coautoría con el Dr. Cristóbal Navarro y Dr. Héctor Ferrada. Se titula «GGArray: A Dynamically Growable GPU Array«. El objetivo de este trabajo consiste en la implementación de un arreglo que pueda aumentar su tamaño durante la ejecución de un programa en GPU. Los arreglos son la estructura más básica para guardar múltiples datos en programación y las variantes con la capacidad de cambiar de tamaño según se requiera (arreglos dinámicos) son las estructuras más utilizadas por su simpleza y versatilidad. Sin embargo, su uso en una GPU resulta extremadamente complejo. Este trabajo explora la posibilidad de aprovechar el alto poder de cómputo de las GPU en aplicaciones que requieren el uso de arreglos dinámicos.
El tercer estudiante que participa con presentación de un artículo es Rodrigo Stevenson Regla, en coautoría con el Dr. Cristóbal A Navarro. El artículo se titula «GPU Voronoi Diagrams for Random Moving Seeds«. Los diagramas de Voronoi son una de las estructuras más básicas de la geometría computacional, y son en particular bastante atractivos en varios campos de investigación debido a la semejanza de los diagramas a variadas estructuras naturales. El trabajo realizado propone una forma de calcular los diagramas de Voronoi dinámicos, básicamente aquellos que cambian con el tiempo. Para lograr esto se ocupa el potencial de cómputo de las tarjetas gráficas en conjunto con técnicas del estado con lo cual se logra elaborar un método eficiente en tiempo de cómputo que puede ser bastante llamativo para investigaciones en diversos campos como la biología o la robótica.
El cuarto artículo que participa corresponde a Sebastián Pacheco Cáceres en coautoría con el Dr. Héctor Ferrada, y se titulad “W-tree – Una nueva estructura de datos dinámica para la administración de claves ordenadas en memoria principal”.
Este artículo participa en la categoría Encuentro de Tesistas 2022 y describe que en la mayoría de los experimentos computacionales se necesita administrar y ordenar la información que será procesada. Para mantener este orden mientras se agregan y eliminan datos (claves) se utilizan estructuras de datos, donde encontramos a los árboles de ordenamiento y sus más de 20 variaciones. Los más utilizados para casos comunes suelen ser los simples árboles de búsqueda binaria (BST), árboles rojo-negro (RB-trees) y los árboles B (B-tree). Este trabajo propone una nueva variación, denominada árbol W (W-tree), que considera un parámetro ‘k’ que corresponde a la cantidad máxima de claves ordenadas en un nodo, y a su vez limita a ‘k-1’ la cantidad de punteros descendientes. Esto mantiene una complejidad algorítmica similar a un BST, pero consigue resultados empíricos que reducen a la mitad el tiempo y memoria utilizada, incluso comparándolo con el RB-tree de la librería estándar de C++ (gcc).
Cabe mencionar que todos los estudiantes del Magíster en Informática, además, son egresados de la Escuela de Ingeniería Civil en Informática de la UACh.
Las Jornadas Chilenas de Computación son un evento que se ha desarrollado ininterrumpidamente desde 1993 organizado en forma conjunta entre la Sociedad Chilena de Ciencia de la Computación y universidades nacionales, entre las que cuentan la Universidad Austral de Chile, U. de Chile, Pontificia U. Católica, U. de Santiago, U. de Concepción, U. de Talca, U. Técnica Federico Santa María, U. Católica del Norte, U. Arturo Prat, U. de Tarapacá y U. de La Serena. Este año, se realiza en la Sede Bellavista de la U. San Sebastián.