Recuperación de información en ficheros XES de gran dimensión mediante técnicas de indexación

• Autores: Yosvanys Aponte Báez
• Directores de la Tesis: Alexander Sánchez Díaz (dir. tes.) , Jesús Peral Cortés (codir. tes.)
• Lectura: En la Universitat d'Alacant / Universidad de Alicante ( España ) en 2016
• Idioma: español
• Tribunal Calificador de la Tesis: Rafael Muñoz Guillena (presid.) , Annia García Pereira (secret.) , Juan Carlos Sepúlveda Peña (voc.)
• Enlaces
  • Tesis en acceso abierto en: RUA
• Resumen

  • Introducción. Antecedentes y estado actual del tema:

    Un documento estructurado es aquel que contiene una estructura predefinida con etiquetas, con el objetivo de mostrar la información relevante del mismo. El estándar por excelencia para la representación de un documento estructurado es el XML (Extensible Markup Language en inglés), el cual se define como un metalenguaje que nos proporciona una manera sencilla de definición de lenguajes de etiquetas estructuradas o como un conjunto de reglas semánticas que nos permiten la organización de información de distintas maneras (Harold, 1998).

    El estándar XML fue creado por la W3C, y ha sido ampliamente aceptado y adoptado para la representación e intercambio de información estructurada, motivando así la necesidad cada vez más de almacenar dicha información. Dicha necesidad conllevó a que una inmensa comunidad investigadora se dedicara al estudio y desarrollo de numerosas estrategias para el almacenamiento y la recuperación de información estructurada.

    Según Chaudhri et al. (2003) siempre se ha planteado la distinción entre los XML "centrados en datos" en contraposición con los "centrados en documentos". Los primeros están caracterizados por una estructura relativamente homogénea y un contenido textual fuertemente tipado. En cambio los segundos, se caracterizan por la presencia de contenido mixto, es decir, estructuras muy variables, típicas de los documentos con predominio de contenido textual.

    Entre las primeras propuestas para el almacenamiento de documentos XML, se puede mencionar las bases de datos tradicionales, que se dividen en bases de datos relacionales y bases de datos orientadas a objetos. Para el almacenamiento en una base de datos se requiere del uso de un esquema predefinido, la estructura del documento debe ser trasladada a las diferentes tablas, lo que se pierde el orden de los elementos insertados. Además se requiere de mucho tiempo para la ejecución de los algoritmos de uniones entre las diferentes tablas, sobre todo cuando se procesan consultas complejas. Ejemplos de esta propuesta son: STORED (Deutsch et al., 1999), XREL (Yoshikawa et al., 2001) y XISS/R (Harding et al., 2003).

    Para evitar los altos costes de uniones entre tablas surgieron las llamadas bases de datos nativas XML, las cuales son utilizadas con frecuencia para documentos "centrados en documentos", pero en algunos casos dependiendo de las características del XML y las necesidades del usuario se pueden emplear para XML "centrados en datos". Las bases de datos nativas contienen como unidad fundamental de almacenamiento el modelo lógico del XML e implementan técnicas de indexación optimizadas y algoritmos de búsqueda que aceleran el acceso a la información almacenada. Tamino (Schöning, 2001), TIMBER (Jagadish et al., 2002), eXist (Meier, 2003) y Natix (Brantner et al., 2005) son ejemplos de este tipo bases de datos.

    Por último, las propuestas híbridas que almacenan partes o el documento completo en su forma nativa en diferentes estructuras. Además los usuarios pueden recuperar datos relacionales o datos estructurales utilizando consultas SQL o consultas XQuery respectivamente. Todas estas propuestas tienen en común la implementación de técnicas de indexación y búsqueda para la recuperación eficiente de documentos estructurados. System RX (Vanja et al., 2005) y las implementaciones realizadas por Hall and Strömbäck (2010) y Mlynkova (2008), constituyen ejemplos de esta clasificación.

    Según la definición dada por Lalmas and Baeza-Yates (2009) la recuperación de documentos estructurados trata sobre la recuperación de fragmentos de documentos. La estructura del documento, sea explícitamente proporcionada por un lenguaje de marcado o derivado, es explotada para determinar el fragmento más relevante del documento y retornarlo como respuesta a la consulta. La identificación del fragmento más relevante del documento puede ser utilizado por si mismo para la identificación del documento más relevante a retornar como respuesta a la consulta realizada En comparación con los sistemas de recuperación de información tradicionales, la recuperación de documentos estructurados ha incluido múltiples retos en cuanto a los tipos de consultas que se pueden ejecutar (Liu et al.,2004). Por ejemplo, los sistemas de recuperación de información tradicionales se centran en las consultas solo de contenido (content only queries en inglés), mientras que las técnicas de recuperación de documentos estructurados se centran en las consultas de contenidos y en las consultas de contenido y estructura (content and structure queries en inglés).

    Desde los inicios de la recuperación de documentos estructurados, diferentes autores han discutido múltiples retos o desafíos a tener en consideración. Por ejemplo, la definición de las partes del documento a recuperar y partes del documento a indexar, tratamiento de los elementos anidados, empleo de términos estadísticos, heterogeneidad del esquema, entre otros (Fuhr and Lalmas, 2006).

    El estudio y discusión de estos y otros retos, han llevado consigo al desarrollo e implementación de diferentes técnicas secuenciales de indexación y búsqueda para bases de datos nativas XML. Según Zemmar et al. (2011), entre los criterios más importantes de estas técnicas se encuentran: estructura de datos utilizada por el índice, estructura del índice y los parámetros de entrada y salida del índice. Con respecto al segundo criterio, numerosos autores han propuesto diferentes clasificaciones. La clasificación que utilizamos se basa en los criterios de Hammerschmidt (2006b) y Mohammad and Martin (2010a) y se dividen en: técnicas basadas en caminos, técnicas basadas en nodos, técnicas basadas en secuencías y técnicas híbridas.

    Las técnicas de indexación basadas en caminos (Grimsmo, 2008; Mohammad and Martin, 2010b) crean resúmenes estructurales de todos los caminos mediante el recorrido del árbol XML desde el nodo raíz hasta los nodos hojas. Presentan muy buenas prestaciones en la resolución de consultas simples o que comienzan desde el nodo raíz. Y su principal debilidad está dada en ocasiones con el rápido crecimiento del índice cuando se manejan documentos XML heterogéneos.

    Las técnicas de indexación basadas en nodos (O'Neil et al., 2004; Lu et al., 2011; Assefa, 2012) emplean esquemas de etiquetado que utilizan las posiciones de los nodos dependiendo del recorrido del árbol XML. Se consideran un eslabón fundamental para los algoritmos de uniones estructurales y para los índices de resúmenes estructurales. La principal debilidad que presentan estas técnicas es la cantidad de uniones estructurales que es necesario establecer para procesar consultas complejas. Estas técnicas también son conocidas en la literatura como: esquema de etiquetado, esquema de codificación o esquema de numeración. A diferencia de las técnicas de indexación de caminos estas pueden determinar eficientemente relaciones jerárquicas entre diferentes nodos.

    Las técnicas de indexación basadas en secuencias (Rao and Moon, 2004; Ferragina and Manzini, 2005; Li et al., 2013) tienen como objetivo principal disminuir el tiempo de ejecución de los algoritmos de uniones estructurales. Estos métodos representan tanto a los documentos como a las consultas por secuencias y subsecuencias, de modo que una consulta puede ser procesada mediante el cotejo de la secuencia del documento y de la consulta. Estas técnicas tienen como fortaleza fundamental el procesamiento eficiente de consultas estructurales, ya que no es necesario la utilización de algoritmos de uniones estructurales.

    Las técnicas de indexación híbridas (Liao et al., 2010a; Hsu et al., 2012b; Hsu and Liao, 2013) incluyen de una manera u otra características de las diferentes técnicas descritas anteriormente. De manera general las técnicas de indexación antes mencionadas, no son adecuadas para la manipulación de grandes volúmenes de datos. Por ejemplo, los archivos XES utilizados en la Minería de Procesos por los algoritmos de descubrimiento, en ocasiones almacenan trazas de procesos muy densas y con gran cantidad de datos. Es por eso que la mayoría de estas técnicas de recuperación requieren ser optimizadas para gestionar eficientemente grandes volúmenes de información en formato XML. En escenarios reales donde las anomalías se deberían predecir y analizar en un corto período de tiempo es una tarea crítica. Diferentes investigadores (Hsu et al., 2012a, 2014) se han planteado el diseño de nuevas técnicas secuenciales o el rediseño de las ya existentes a paralelas/distribuidas para el manejo de grandes volúmenes de documentos XML.

    Por otra parte, para las empresas es de vital importancia obtener información detallada sobre sus procesos de negocios, basada fundamentalmente en su funcionamiento y permitiéndoles encontrar anomalías y posibles mejoras. Una solución eficiente a este problema, se encuentra en el área de la Minería de Procesos, donde sus técnicas principales tienen como objetivos: descubrir, mejorar y monitorear los procesos de negocios, a través de la extracción de conocimientos de los registros de eventos que se encuentran disponibles en los actuales sistemas de información. Es una tecnología relativamente joven y a pesar de esto múltiples empresas la están incorporando con la intención de mejorar sus procesos de negocios.

    Los registros de eventos están compuestos por instancias de procesos y cada instancia contiene información relacionada con la ejecución de una acción u operación específica que se ha ejecutado en un sistema y su marca de tiempo correspondiente (Verbeek et al., 2011). Desde el año 2010 la IEEE (Institute of Electrical and Electronics Engineers en inglés) adoptó un nuevo formato para el almacenamiento de los registros de eventos: el estándar XES (eXtensible Event Stream, Gunther and Verbeek, 2009) considerado el sucesor del MXML.

    El principal propósito del estándar XES es ofrecer un formato de intercambio de registros de eventos entre herramientas y dominios de aplicaciones (Arturo et al., 2015). Los registros de eventos contenidos en los ficheros XES, son la entrada de los algoritmos de descubrimiento utilizados por las algunas de las herramientas especializadas como PROM (Gunther and van der Aalst, 2006) y XESame (Buijs, 2010), donde su eficiencia es proporcional al tamaño del fichero. En algunos casos donde los procesos de negocios son muy densos (decenas de millones de trazas) y sea necesario la detección de anomalías en tiempo real, es preciso entonces, la utilización de analizadores sintácticos de ficheros XES eficientes y escalables.

    En el marco del proyecto desarrollado en la Universidad Agraria de la Habana con el Centro de Investigaciones de Tecnologías Integradas de la CUJAE (CITI por sus siglas) se implementaron diferentes algoritmos de descubrimiento que se pusieron en práctica en diferentes escenarios económicos del país. Las prestaciones de los algoritmos se vieron afectadas cuando manipulaban archivos XES de gran dimensión. A partir de aquí surgió la necesidad de diseñar e implementar estrategias de análisis para el manejo eficiente de estos archivos XES de gran dimensión. Se implementaron soluciones que utilizan modelos DOM para la carga en memoria del XES y el empleo de analizadores lazy. Dichas soluciones no fueron del todo eficientes para escenarios que manipulan grandes volúmenes de datos en tiempo real.

    Objetivos de la investigación:

    Objetivo general:

    •Diseñar nuevos mecanismos de indexación para el manejo eficiente de consultas en tiempo real en archivos densos en formato XES Objetivos específicos:

    •Proponer una estructura de índice basada en el modelo lógico del XES y que se pueda paginar en memoria.

    •Definir métodos que optimicen el tiempo de construcción del índice, apoyados en un esquema de compresión del XES.

    •Optimizar el coste temporal de ejecución de las consultas sobre el índice mediante el uso de estructuras basadas en arreglos de sufijos, árboles ternarios de búsquedas y estructuras Rank/Select.

    •Proponer variantes paralelas/distribuidas de los algoritmos de construcción de índices creados y evaluar su eficiencia, escalabilidad y aceleración.

    •Definir mecanismos de consulta que aprovechen la estructura distribuida del índice.

    Metodologia, hipótesis y plan de trabajo:

    A pesar de lo positivo de las técnicas de indexación para la recuperación eficiente de documentos XML antes mencionadas, pueden presentarse algunas limitaciones. Por ejemplo, necesidad de grandes volúmenes de memoria para almacenamiento de la estructura del índice, donde en algunos casos puede ser mayor que el documento original (Chen et al., 2005). En otros casos, para reducir al mínimo el tamaño de la estructura del índice es necesario un tiempo de ejecución crítico y generalmente su rendimiento se reduce cuando se analizan grandes documentos XML. Finalmente, la mayoría de las técnicas están confinadas a pequeñas colecciones de datos que se ejecutan de forma secuencial. El estudio de Liao et al. (2010b) plantea la creación de nuevas técnicas de indexación o la adaptación de las ya creadas a entornos paralelos/distribuidos para lograr una manipulación eficiente de grandes volúmenes de datos.

    Por otra parte, el estudio de las dos grandes áreas de investigación: Recuperación de información estructurada y Minería de Procesos (manejo eficiente de los ficheros densos de trazas), en el marco del proyecto PRONEG (Procesos de Negocios) de la Universidad Agraria de La Habana, ha conllevado a la convergencia de un área de investigación motivada por la necesidad del manejo eficiente de archivos XES de gran dimensión. Motivo del cual se definió el problema de investigación que plantea: ¿Cómo reducir los costes de procesamiento de archivos densos de trazas para favorecer el análisis de modelos de procesos en tiempo real? La novedad científica de esta investigación radica en el diseño de nuevas estrategias basadas en el manejo eficiente de índices estructurales y de contenidos para recuperar información en tiempo real en archivos XES de gran dimensión. Además presenta las siguientes novedades prácticas:

    •Implementación de algoritmos de optimización mediante técnicas paralelas/distribuidas para reducir los tiempos de construcción del índice de contenido del XES y su almacenamiento en memoria.

    •Diseño de nuevos métodos para el manejo de archivos XES de gran tamaño utilizando índices, mediante la adaptación de estructuras de datos utilizadas en sistemas tradicionales de recuperación de información estructurada.

    •Estudio comparativo de los costes temporales de las versiones secuenciales y paralelas/distribuidas.

    Para llevar a cabo el trabajo se establece las siguientes tareas:

    •Estudio del estado actual del tema de las técnicas de indexación secuencias y paralelas/distribuidas. Analizar propuestas para el manejo eficiente de grandes volúmenes de información en la Minería de Procesos para mejorar la eficiencia de los algoritmos de descubrimiento.

    •Diseño de una estrategia de compresión para mejorar los costes de procesamiento durante la etapa de análisis de un XES.

    •Definición e implementación de un índice estructural XES basado en el modelo lógico del XES que se permita almacenar en memoria la estructura de un XES.

    •Diseño de una propuesta de índice de contenido basado en los clasificadores de eventos de un XES.

    •Diseño de mecanismos de consultas que permitan manejar la información almacenada en el índice estructural y de contenido.

    •Realización de pruebas experimentales para la validación de las propuestas.

    Conclusiones:

    A partir del estudio de la estructura lógica del estándar XES, se diseñaron diferentes estrategias de indexación, que permiten consultar la información almacenada en los registros de eventos de una manera más eficiente. De esta forma se facilita el análisis en tiempo real de los algoritmos de descubrimiento de modelos usados en la Minería de Procesos.

    Las estrategias se basan en la construcción de índices estructurales e índices de contenidos, ajustados al modelo lógico de datos del estándar XES, lo que permite manejar grandes volúmenes de información contenida en los registros de eventos. Se definió el esquema de un índice estructural, formado por un resumen de los caminos del árbol, según el esquema de un XES, desde el nodo raíz hasta los nodos hojas. Este índice representa de una forma compacta la información estructural almacenada en un archivo en formato XES.

    Se describió cómo es posible implementar este índice estructural utilizando arreglo de sufijos, donde cada elemento del arreglo corresponde con una referencia al sufijo más pequeño del resumen estructural de caminos en orden lexicográfico. El índice permite la ejecución de consultas estructurales con relaciones directas e indirectas. Una consulta estructural con relaciones directas, implica realizar dos búsquedas binarias en el arreglo de sufijos.

    Para disminuir los costes temporales de las dos búsquedas binarias es posible manejar un árbol ternario de búsqueda como estructura de datos auxiliar. Este árbol ternario almacena en los nodos internos los sufijos del resumen estructural de caminos y en los nodos hojas se almacena el rango máximo de posiciones en el arreglo de sufijos. Se comprobó que el empleo de una secuencia de posiciones textuales para cada camino, permite que durante la recuperación de los eventos de cada traza se obtengan en orden cronológico las actividades asociadas a los eventos.

    Se ha definido una estrategia de compresión para los ficheros XES, apoyada en la repetición de los atributos string. Esta se basa en la unificación de todos los nodos del árbol de tipo \emph{string} que describen los atributos de un evento. Para lograrlo se crea un nuevo atributo a la traza en la cual están contenidos los eventos. Se comprobó que el empleo de esta estrategia de compresión disminuye la cantidad de nodos y con ellos los costes temporales en la etapa de análisis sintáctico de un fichero en formato XES.

    Se definió el esquema de un índice de contenidos XES, basado en los valores de los clasificadores de eventos. Se presentó una implementación secuencial mediante el empleo de las estructuras de datos sucintas o diccionarios rank/select. Presentamos además una estrategia paralela/distribuida para la construcción del índice de contenidos XES, sobre la plataforma Hadoop y su paradigma de programación MapReduce. La estrategia planteada es capaz de construir fragmentos de un documento XES como respuesta a una consulta, sin necesidad de acceder al documento original. Se verificó que el incremento de los nodos del clúster Hadoop disminuye los costes temporales de construcción del índice de contenidos. Se comprobó que mediante una distribución de los datos, no se ve afectado el tiempo de construcción del índice de contenidos cuando se incrementa el tamaño del archivo XES.

    Finalmente, se ha demostrado que el empleo de estrategias de índices que aprovechan la estructura del XES, son más eficientes que los modelos que cargan el XES completamente en memoria y que los modelos que utilizan analizadores lazy. Además, un índice de este tipo generado a partir de la estructura lógica del XES, permite que su construcción sea optimizada y personalizada para los diferentes algoritmos de descubrimiento de modelos en la Minería de Procesos (por ejemplo, el algoritmo Fuzzy Minner).