Efficient query processing for multigranular data.

dc.contributor.advisorRodríguez, Andreaen
dc.contributor.advisorSeco, Diegoen
dc.contributor.authorGatica Romero, Diego
dc.date.accessioned2024-03-20T18:03:50Z
dc.date.accessioned2024-08-28T21:31:24Z
dc.date.available2024-03-20T18:03:50Z
dc.date.available2024-08-28T21:31:24Z
dc.date.issued2024
dc.descriptionTesis para optar al grado de Doctorado en Ciencias de la Computaciónes
dc.description.abstractSpatial 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.en
dc.description.campusConcepción.es
dc.description.departamentoDepartamento de Ingeniería Informática y Ciencias de la Computaciónes
dc.description.facultadFacultad de Ingeniería.es
dc.identifier.urihttps://repositorio.udec.cl/handle/11594/11897
dc.language.isoenen
dc.publisherUniversidad de Concepciónes
dc.rightsCC BY-NC-ND 4.0 DEED Attribution-NonCommercial-NoDerivs 4.0 Internationalen
dc.rights.urihttps://creativecommons.org/licenses/by-nc-nd/4.0/en
dc.subjectMultigranular dataen
dc.subjectGranularityen
dc.titleEfficient query processing for multigranular data.en
dc.typeTesises

Files

Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
gatica_r_d_2024_DOC.pdf
Size:
4.48 MB
Format:
Adobe Portable Document Format
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.71 KB
Format:
Plain Text
Description:

Collections