Browsing by Author "Gatica Romero, Diego"

Now showing 1 - 3 of 3
  • Thumbnail Image
    Item
    Efficient query processing for multigranular data.
    (Universidad de Concepción, 2024) Gatica Romero, Diego; Rodríguez, Andrea; Seco, Diego
    Spatial and temporal attributes are typical examples of data that can be represented at different levels of granularity or resolution. The massive amount of this type of data makes it impractical to store and process data without making use of efficient algorithms and structures. In search of a way to handle multigranular data, several data models have been proposed; however, there is no efficient implementation in terms of space usage and query time for any of the various existing models for handling multigranular data. In this thesis, we study algorithms and data structures to process different queries on multigranular models, specifically, the work done uses succinct data structures and achieves a good trade-off between space usage and query time. In particular, we start by proposing a succinct data structure and algorithm for the implementation of a multigranular model that is general enough to be used in different domains. This model is based on the relations of subsumption and disjoint between its elements (i.e. granules), and their respective negations, and it proposes the strategy of deriving new relations, in order to reduce the space to be used. The proposed structure used (|E| − |V |) log2 |V | + O(|E|) space to store a graph with V vertices and E edges to store a graph that represent the subsumption relation, plus |Er| log |V|+|Er|+|V |+o(|Er| + |V |) for for each of the other relationships, and improves the derivation of new relations, compared to other implementations. A second succinct data structure is proposed, with a focus on the spatial domain by providing algorithms for processing topological queries like inclusion, disjointness, and adjacency between regions on a multi resolution context. In the case of a set of n regions without a hierarchy, we can manipulate it efficiently using 4n + o(n) bit, for the case when we have a hierarchy of height h, our structure proposed requires as little as O(n log h) bits, while maintaining a similar query time compared to a non-compact implementation.
  • Thumbnail Image
    Item
    Implementación modelo de datos multigranular basado en reglas de inferencias.
    (Universidad de Concepción, 2019) Gatica Romero, Diego; Rodríguez, Andrea
    Frente al problema de poseer bases de datos con datos a distintos niveles de detalle (granularidad), el modelo multigranular presenta ventajas sobre el modelo relacional clásico. En un modelo relacional clásico, una instancia debe contener toda la información que caracterice la estructura granular a través de relaciones con claves foráneas. El modelo multigranular, por otro lado, crea una única estructura para representar las diversas granularidades y los gránulos que las componen. Una estructura multigranular permite que distintas instancias de bases de datos hagan referencia a esta estructura sin duplicación de información, y al mismo tiempo permite que instancias tengan distintos de niveles de granularidad que puedan ser integrados a través de ´esta estructura. En este trabajo se presenta una implementación de un modelo multigranular que busca minimizar el espacio de almacenamiento junto con un tiempo de procesamiento comparable al tiempo que tendría procesar consultas en un modelo relacional clásico.
  • Thumbnail Image
    Item
    Modelo base de datos multigranular
    (Universidad de Concepción, 2018) Gatica Romero, Diego; Rodríguez, Andrea
    La información puede encontrarse a distintos niveles de granularidad, y aunque actualmente hay diversos modelos de bases de datos enfocados a instancias particulares, ninguno de estos aborda la granularidad de los datos. En esta memoria de título se diseñó un modelo que explota la multigranularidad de los datos y los operadores básicos necesarios para la realización de consultas sobre este modelo. Los resultados mostraron la eficiencia temporal de los operadores implementados sobre el modelo propuestos aunque en término espacial no demostró un ahorro con relación a la instancia inicial de prueba.
Síguenos en...