Resumen de Métodos de acceso a grandes colecciones de documentos y su paralelización
Fernando José Artigas Fuentes
La motivación fundamental de esta tesis es abordar el problema de la recuperación de información por semejanza sobre repositorios de documentos textuales. Dado un documento como consulta, su objetivo es recuperar del repositorio aquellos documentos estrechamente relaciones con el mismo, según la medida de semejanza utilizada. La mayoría de los métodos de la literatura sufren del problema conocido como "maldición de la dimensionalidad". Debido a ello pierden prestaciones o no pueden ser aplicados a este tipo de problema que involucra espacios de representación de decenas de miles de dimensiones, entendiendo como tales a cada uno de los términos distintos en los documentos del respositorio. En esta tesis se presentan un conjunto de métodos de acceso aproximados secuenciales y paralelos que realizan de manera eficiente y con resultados de alta calidad este proceso de recuperación.
En este trabajo se presentan y evalúan diferentes aproximaciones al problema del indizado y búsqueda sobre colecciones estáticas de objetos. En este sentido se proponen dos métodos generales de acceso aproximados basados, el primero de ellos en un grafo, fruto de la combinación de dos estructuras de la literatura, como son los grafos conexos y los grafos kNNG; el segundo método, una generalización, que hace uso de múltiples grafos para afrontar el mismo problema, reduciendo ostensiblemente el coste del indizado del repositorio y mejorando la calidad de los resultados.
La necesidad de procesar de manera eficiente grandes repositorios y flujos de consultas dio lugar al desarrollo de variantes paralelas de los métodos propuestos, mediante el uso de esquemas clásicos de la literatura como son el maestro-esclavo, el esquema farm y el procesamiento en tubería. Además de que se hizo uso tanto de arquitecturas paralelas con memoria compartida mediante la biblioteca de funciones OpenMP, como de clusters de ordenadores con memoria distribuida mediante la interfaz de comunicaciones MPI. Además, el uso de herramientas ampliamente difundidas ha dado lugar a implementaciones portables de los métodos.
A diferencia de la mayoría de las propuestas de métodos de acceso que aparecen en la literatura, nuestras aproximaciones son poco afectadas por el problema de la maldición de la dimensionalidad, y aunque devuelven soluciones aproximadas, estas son de alta calidad cuando son comparadas con las obtenidas por el método exacto basado en la búsqueda exhaustiva.
Los métodos de acceso propuestos sirven, además, como base para el desarrollo de otras tareas de la Minería de Textos, como por ejemplo la clasificación de documentos. En este trabajo hemos propuesto un nuevo clasificador k-NN con el que se obtienen resultados comparables o superiores a los obtenidos con otros clasificadores del mismo tipo tomados de la literatura.
La experimentación realizada sobre varias y diversas colecciones de prueba, permite constatar la alta calidad de los resultados y la eficiencia con que se han obtenido para nuestras aproximaciones, demostrando su aplicabilidad como métodos de acceso para la recuperación de información sobre espacios de representación de decenas de miles de dimensiones.
