Efficient query processing for multigranular data.

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.