“Tunneling on Wheeler Graphs” es el nombre del artículo de investigación coescrito por los académicos del Departamento de Ciencias de la Computación (DCC) de la Universidad de Chile, Gonzalo Navarro; y de la Escuela de Informática y Telecomunicaciones de la Universidad Diego Portales, Travis Gagie; en conjunto con los investigadores de postgrado de la Universidad de Helsinky, Jarno Alanko; y de la Universidad de Siegen, Louisa Seelbach, que obtuvo el premio Capocelli 2019 al mejor artículo de investigación realizado y presentado por un estudiante en la Data Compression Conference 2019 (DCC 2019).

El reconocimiento que anualmente se entrega en memoria del investigador y colaborador de la conferencia DCC, Renato M. Capocelli (1940-1992), fue otorgado a los autores de “Tunneling on Wheeler Graphs” por la “relevancia de sus resultados en el área de investigación en indexación comprimida”, resolvió el comité de revisores de DCC 2019.

Según explicó el académico del DCC y coautor de “Tunneling on Wheeler Graphs”, Gonzalo Navarro, el paper abarca tres grandes tópicos: la Transformación de Burrows-Wheeler (BWT), un paradigma de compresión que, además de ser usado en compresores exitosos como el algoritmo bzip2, permite efectuar búsquedas eficientes en textos comprimidos; los Grafos de Wheeler (Wheeler Graphs), una generalización que permite extender la BWT no sólo a textos sino también a árboles y grafos de datos; y una técnica llamada tunelización (tunneling), que permite comprimir mejor otro tipo de redundancias que aparecen en la BWT.

“Lo que demostramos en este artículo fue que una técnica para explotar las redundancias como el tunneling se puede generalizar a Wheeler Graphs, lo cual, además de comprimir mejor, también permite indexar, es decir, continuar realizando búsquedas en objetos comprimidos. De este modo, combinamos la generalización de la BWT, la mejora en la compresión y la búsqueda” recalcó el profesor Navarro.

El académico del DCC destacó, además, que “Tunneling on Wheeler Graphs” llegó en un buen momento, pues este año, además, se cumplen 25 años desde la creación de la BWT por parte de los investigadores Michael Burrows y David Wheeler.

“El mérito de Travis Gagie y mío fue proponer el tema a Jarno Alanko y Louisa Seelbach y guiarlos en este proceso. De hecho, les sugerimos que lo presentaran a dúo para que ambos pudieran ganarse el premio y lo hicieron muy bien”, destacó el profesor Gonzalo Navarro, quien también reveló que “sospechábamos que podrían ganar por la belleza conceptual de este trabajo”.

Acerca de la importancia del reconocimiento, el académico del DCC reveló que el Premio Capocelli tiene un altísimo valor para los estudiantes y que, tras recibirlo, “tanto Jarno Alanko como Louisa Seelbach, le manifestaron su alegría y agradecimiento por haber recibido un estímulo así para impulsar sus carreras”, concluyó.

--
Comunicaciones DCC