Efficient query processing for multigranular data.
Loading...
Date
2024
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Universidad de Concepción
Abstract
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.
Description
Tesis para optar al grado de Doctorado en Ciencias de la Computación
Keywords
Multigranular data, Granularity