Manuel Cáceres con su tesis de Magíster "Compressed Suffix Trees for Repetitive Collections Based on Block Trees", guiada por el profesor del Departamento de Ciencias de la Computación Gonzalo Navarro, obtuvo el tercer lugar en el concurso Latinoamericano de Tesis de Maestría (CLTM), organizado por el Centro Latinoamericano de Estudios en Informática (CLEI), y cuyo premio involucra la presentación de la investigación en la XLVI Conferencia Latinoamericana de Informática que se realizará este año de forma online en Loja, Ecuador, entre el 19 y el 23 de Octubre. 

En la investigación realizada por Manuel Cáceres, se estudió el uso de Block Trees en la construcción de un árbol de sufijos comprimidos. “El árbol de sufijos es una estructura de datos muy versátil que ha permitido solucionar problemas complejos de manera eficiente en diversas áreas, como por ejemplo stringología, bioinformática o document retrieval. Sin embargo, su elevado uso de memoria hace que no sea factible utilizarlo cuando se trabaja con grandes volúmenes de datos. De aquí nace la necesidad de construir árboles de sufijos comprimidos”, explicó Manuel.

La principal idea de esta investigación fue aprovechar la repetitividad de los datos con los que se está trabajando para construir un nuevo árbol de sufijos comprimido especializado en datos repetitivos. “Esta repetitividad en los datos se encuentra por ejemplo en la historia de versiones de un documento como Wikipedia o un repositorio de software, o al estudiar un conjunto de genes en una población”, destacó Manuel y agregó: “para esto usamos Block Trees, una estructura de datos que captura esta repetitividad y responde eficientemente consultas de acceso y rank/select. En la tesis modificamos esta estructura para construir un árbol de sufijos comprimido que hereda las propiedades de espacio y eficiencia de los Block Trees, lo que confirmamos experimentalmente”, señaló.

A su vez, destacó que el área de investigación en el que está inmersa su tesis, que es estructuras de datos comprimidas, ha estado recibiendo especial atención por parte de la comunidad científica. En particular el estudio de colecciones repetitivas, tanto en el ámbito teórico como práctico. “En este sentido mi tesis posee un fuerte componente teórico, al estudiar y proponer estructuras de datos, y al mismo tiempo una amplia evaluación experimental de las técnicas propuestas, que corroboran nuestras hipótesis”, enfatizó.

Para finalizar, Manuel, quien hoy se encuentra en su segundo semestre de doctorado en la Universidad de Helsinki, en Finlandia, destacó que “este premio vuelve a validar que la investigación que se hace en el DCC tiene impacto a nivel internacional, en particular, en el grupo de investigación de estructuras de datos comprimidas, donde el departamento es uno de los pioneros en el mundo. Mientras que, a nivel personal, me alegra este reconocimiento a mi trabajo, ya que me brinda la oportunidad de presentar mi investigación a un público más amplio y diverso del que he tenido la oportunidad hasta ahora. Esto porque además de recibir el reconocimiento, podré presentar mi trabajo en la ceremonia de la Conferencia”, concluyó.

--
Comunicaciones DCC