El Dr. Oyarzún defendió con éxito una tesis sobre el uso de índices comprimidos para la recuperación de información

11 de mayo, 2015

El martes 5 de mayo el candidato Mauricio Oyarzún Silva defendió exitosamente su tesis doctoral “Índices Comprimidos para Recuperación de Información” para la obtención del Doctorado en Ciencias de la Ingeniería, mención en Informática. La defensa se realizó en la Sala de Conferencias del DIINF y contó con la presencia del Decano de la Facultad de Ingeniería,  Msc Juan Carlos Espinoza, además de una concurrida asistencia. Con posterioridad se ofreció un vino de honor a todos los participantes.

Durante el desarrollo de sus estudios doctorales el Dr. Oyarzún realizó una publicación en revista indexada y dos publicaciones en conferencias de alto nivel en conjunto con su profesor guía, el Dr. Mauricio Marín, académico titular del programa.

El Dr. Oyarzún inició sus estudios de Doctorado el 2008, mismo año que se titulaba de Ingeniero Civil en Computación e Informática en la Universidad Arturo Prat. Comenta que tomó la decisión de continuar inmediatamente sus estudios de postgrado porque le “llama la atención la obtención de conocimiento, ya que vengo de una familia de profesores”. Esto coincidió con la oportunidad de conocer al Dr. Mauricio Marín en las Jornadas Chilenas de Computación de Iquique el año 2007, cuando surgió la curiosidad de conocer sobre los motores de búsqueda, un tema que en ese momento le era desconocido.

La tesis intenta hacer índices más eficientes para recuperar la información de la web. “Un ejemplo de índice son los que salen al final de los libros, con términos importantes y la página del libro en la que salen, esto es los mismo, pero busca inexar toda la web, para poder encontrar más fácilmente la información” explica el Dr. Oyarzún. En el caso de esta tesis doctoral se hicieron experimentos usando Trec Gov2, un corpus que contiene todas las web de datos gubernamentales de EEUU el año 2006.

Las tesis desarrolladas en el Doctorado en Ciencias de la Ingeniería, mención en Informática, tienen como requisito enfocarse en la búsqueda de conocimiento en zonas de frontera, abarcando temáticas innovadoras. En este caso, la tesis investigó la aplicación de una estructura novedosa, el wavelet tree, “que guarda todo el texto, pero permite recuperar partes de este. Por primera vez lo vimos como motor de búsqueda, ya que su uso original era sólo la recuperación de textos” explica.

Otro requisito para les tesis doctorales en el área informática es la aplicabilidad. En este caso, la tesis trabajó con una estructura que tiene varias décadas de desarrollo, como son los “índices invertidos”, pero con una metodología diferente llamada Run Length Encoding que “busca aprovechar la gran cantidad de unos existentes en la web. Por primera vez aprovechamos este conocimiento de que la web tiene una gran cantidad de unos y los tratamos como si fueran un sólo rango, ahorrando espacio” indica el Dr. Oyarzún. En  la actualidad se están realizando proyectos que aplican estos cambios en Yahoo!

Consultado por la experiencia de vida que le deja haber realizado su formación en la UdeSantiago, el Dr. Oyarzún destaca la buena recepción de parte de los profesores, a quienes caracteriza como pacientes y acogedores. También destaca el desarrollo de habilidades que no tenía al inicio del programa tales como tolerancia a la presión, la disciplina y el rigor científico. Finalmente, agradece  a Yahoo! Research Chile, por el financiamiento recibido.

Tesis Doctoral

Título: Índices Comprimidos para Recuperación de Información

Autor: Dr. Mauricio Oyarzún Silva

Profesor Guía: Dr. Mauricio Marín Caihuan

Profesor Co-Guía: Dr. Diego Arroyuelo

Comisión Examinadora: Dr. Diego Seco Naveiras, Dr. Mario Inostroza, Dr. Fernando Rannou y Dra. Erika Rosas

Resumen:

El índice invertido ha llegado a ser un estándar de facto en Recuperación de Información, y en la literatura técnica existe una amplia gama de métodos de compresión y variantes que permiten ejecutar eficientemente las tareas de un motor de búsqueda. Sin embargo, en los últimos años, en la literatura también se han propuesto estructuras auto-indexadas que podrían ser una alternativa al índice invertido.

Este trabajo de tesis se centra en los auto-índices comprimidos, en particular el wavelet tree, desde la perspectiva de la recuperación de información y sus funciones más básicas como son la recuperación e intersección de listas o la recuperación de snippets. Proponemos una serie de métodos para realizar estas tareas de manera tan eficiente como lo haría un índice invertido. Además, nos preocupamos de la escalabilidad del problema proponiendo metodologías para realizar las mismas operaciones de nuestro sistema de recuperación de información basado en auto-índices en ambientes paralelos. Otra rama de investigación relacionada es la compresión de índices invertidos. Esta tesis aborda esta temática proponiendo novedosos métodos de compresión de enteros que aprovechan la presencia de documentos contiguos en las listas invertidas para conseguir mejores resultados en espacio y tiempo de descompresión. Realizamos además técnicas de reordenamiento para generar documentos contiguos cuando no están presentes en la coleción y asi favorecer nuestros nuevos métodos de compresión.

Palabras Claves: recuperación de información, auto-índices, motores de búsqueda en la web, compresión de enteros, índices invertidos, paralelismo, wavelet tree.

Publicaciones asociadas:

  • Distributed Search based on Self-Indexed Compressed Text. In Information Processing and Management, Elsevier, September 2012. 48(5): 819-827.
  • Run-Length Compressed Inverted Indexes with Higher Compression Ratio and Faster Query Processing. In proc. of 36th International ACM SIGIR conference on research and development in Information Retrieval (SIGIR 2013), Dublin,Ireland. 2013. 173-182.
  • Compressed Self-Indices Supporting Conjunctive Queries on Document Collections. In 17th String Processing and Information Retrieval Symposium (SPIRE 2010), Los Cabos, Mexico. 2010. 43-54.