Abstract In this work we address the problem of speeding up navigational queries over compact planar graphs. In particular, we work over one of the most practical representations for compact planar graphs, which is based on the decomposition of the graph into one arbitrary spanning tree and a second one induced by the former. We propose a new optimization model that captures the desired topological properties of the first spanning tree. For this model, we propose several heuristics, which we experimentally compare on our application domain. The experimental results support that the model indeed captures the main properties that allow us speeding up the main navigational queries over several benchmarks.

Abstract A raster time series is a sequence of independent rasters arranged chronologically covering the same geographical area. These are commonly used to depict the temporal evolution of represented variables. The $T$-$k^{2}$-raster is a compact data structure that performs very well in practice for compact representations for raster time series. This structure classifies each raster as a snapshot or a log and encodes logs concerning their reference snapshots, which are the immediately preceding selected snapshots. An enhanced version of the $T$-$k^{2}$-raster, called Heuristic $T$-$k^{2}$-raster, incorporates a heuristic for automating the selection of snapshots. In this study, we investigate the optimality of the heuristic employed in Heuristic $T$-$k^{2}$-raster by comparing it with a dynamic programming (DP) approach. Our experimental evaluation demonstrates that Heuristic $T$-$k^{2}$-raster is a near-optimal solution, achieving compression performance almost identical to the DP method. These results indicate that variations of the structure that maintain the temporal order of the rasters are unlikely to significantly improve compression. Consequently, we explore an alternative approach based on clustering, where rasters are grouped according to their similarity, regardless of their temporal order. Our experimental evaluation reveals that this clustering-based strategy can enhance compression in scenarios characterized by cyclic behaviour.

Abstract Conventional database systems function as static data repositories, storing vast amounts of facts and offering efficient query processing capabilities. The sheer volume of data these systems store has a direct impact on their scalability, both in terms of storage space and query processing time. Deductive database systems, on the other hand, require far less storage space since they derive new knowledge by applying inference rules. The challenge is how to efficiently obtain the required derivations, compared to having them in explicit form. In this study, we concentrate on a set of predefined inference rules for subsumption and disjointness relations, including their negations. We use compact data structures to store the facts and provide algorithms to support each type of relation, minimizing even further the storage space requirements. Our experimental findings demonstrate the feasibility of this approach, which not only saves space but is often faster than a baseline that uses well‐known graph traversal algorithms implemented on top of a traditional adjacency list representation to derive the relations.

Microservices architecture advocates decentralized data ownership for building software systems. Particularly, in the Database per Service pattern, each microservice is supposed to maintain its own database and to handle the data related to its functionality. When implementing microservices in practice, however, there seems to be a paradox: The de facto technology (i.e., containerization) for microservice implementation is claimed to be unsuitable for the microservice component (i.e., database) in production environments, mainly due to the data persistence issues (e.g., dangling volumes) and security concerns. As a result, the existing discussions generally suggest replacing database containers with cloud database services, while leaving the on-premises microservice implementation out of consideration. After identifying three statelessness-dominant application scenarios, we proposed container-native data persistence as a conditional solution to enable resilient database containers in production. In essence, this data persistence solution distinguishes stateless data access (i.e., reading) from stateful data processing (i.e., creating, updating, and deleting), and thus it aims at the development of stateless microservices for suitable applications. In addition to developing our proposal, this research is particularly focused on its validation, via prototyping the solution and evaluating its performance, and via applying this solution to two real-world microservice applications. From the industrial perspective, the validation results have proved the feasibility, usability, and efficiency of fully containerized microservices for production in applicable situations. From the academic perspective, this research has shed light on the operation-side micro-optimization of individual microservices, which fundamentally expands the scope of “software micro-optimization” and reveals new research opportunities.

A common technique to design compact representations for planar graphs is to decompose the graph into spanning trees, which are later represented compactly. In some representations of planar graphs, such as Turan's representation, the topology of such spanning trees is not fixed. In this work, we show that the topology of the spanning trees used in the representation impacts the performance of typical operations of compact planar graphs. Hence, by computing suitable spanning trees and improving their compact representation, we provide compact representations of planar graphs that are both smaller and faster than the state of the art.

The topological model for spatial objects identifies common boundaries between regions, explicitly storing adjacency relations, which not only improves the efficiency of topologyrelated queries, but also provides advantages such as avoiding data duplication and facilitating data consistency. Recently, a compact representation of the topological model based on planar graph embeddings was proposed. In this article, we provide an elegant generalization of such a representation to support hierarchies of vector objects, which better fits the multi-granular nature of spatial data, such as the political and administrative partition of a country. This representation adds a small space on top of the succinct base representation of each granularity, while efficiently answering new topology-related queries between objects not necessarily at the same level of granularity.

Abstract We consider the problem of designing a succinct data structure for representing the connectivity of planar triangulations. The main result is a new succinct encoding achieving the information-theory optimal bound of 3.24 bits per vertex, while allowing efficient navigation. Our representation is based on the bijection of Poulalhon and Schaeffer (Algorithmica, 46(3):505–527, 2006) that defines a mapping between planar triangulations and a special class of spanning trees, called PS-trees. The proposed solution differs from previous approaches in that operations in planar triangulations are reduced to operations in particular parentheses sequences encoding PS-trees. Existing methods to handle balanced parentheses sequences have to be combined and extended to operate on such specific sequences, essentially for retrieving matching elements. The new encoding supports extracting the d neighbors of a query vertex in O(d) time and testing adjacency between two vertices in O(1) time. Additionally, we provide an implementation of our proposed data structure. In the experimental evaluation, our representation reaches up to 7.35 bits per vertex, improving the space usage of state-of-the-art implementations for planar embeddings.

Raster time series, a.k.a. temporal rasters, are collections of rasters covering the same region at consecutive timestamps. These data have been used in many different applications ranging from weather forecast systems to monitoring of forest degradation or soil contamination. Many different sensors are generating this type of data, which makes such analyses possible, but also challenges the technological capacity to store and retrieve the data. In this work, we propose a space-efficient representation of raster time series that is based on Compact Data Structures (CDS). Our method uses a strategy of snapshots and logs to represent the data, in which both components are represented using CDS. We study two variants of this strategy, one with regular sampling and another one based on a heuristic that determines at which timestamps should the snapshots be created to reduce the space redundancy. We perform a comprehensive experimental evaluation using real datasets. The results show that the proposed strategy is competitive in space with alternatives based on pure data compression, while providing much more efficient query times for different types of queries.

The raster model is widely used in Geographic Information Systems to represent data that vary continuously in space, such as temperatures, precipitations, elevation, among other spatial attributes. In applications like weather forecast systems, not just a single raster, but a sequence of rasters covering the same region at different timestamps, known as a raster time series, needs to be stored and queried. Compact data structures have proven successful to provide space-efficient representations of rasters with query capabilities. Hence, a naive approach to save space is to use such a representation for each raster in a time series. However, in this paper we show that it is possible to take advantage of the temporal locality that exists in a raster time series to reduce the space necessary to store it while keeping competitive query times for several types of queries.

We introduce a new technique for the efficient management of large sequences of multi-dimensional data, which takes advantage of regularities that arise in real-world datasets and supports different types of aggregation queries. More importantly, our representation is flexible in the sense that the relevant dimensions and queries may be used to guide the construction process, easily providing a space-time tradeoff depending on the relevant queries in the domain. We provide two alternative representations for sequences of multidimensional data and describe the techniques to efficiently store the datasets and to perform aggregation queries over the compressed representation. We perform experimental evaluation on realistic datasets, showing the space efficiency and query capabilities of our proposal.

We present two compact representations of rasters, which are used in GIS to represent temperatures, elevations, and other spatial attributes, that support queries on the positions and/or the values stored. These representations are based on space-filling curves and recent advances on compact data structures. They are practical, competitive with recent works on the problem, and present some improved characteristics, such as a nice generalization to time series of rasters, i.e. the storage of several rasters covering the same area at different times.

Real-world point sets tend to be clustered, so using a machine word for each point is wasteful. In this paper we first bound the number of nodes in the quad tree for a point set in terms of the points' clustering. We then describe aqua tree data structure that uses O (1) bits per node and supports faster queries than previous structures with this property. Finally, we present experimental evidence that our structure is practical.

A spatial data set is consistent if it satisfies a set of integrity constraints. Although consistency is a desirable property of databases, enforcing the satisfaction of integrity constraints might not be always feasible. In such cases, the presence of inconsistent data may have a negative effect on the results of data analysis and processing and, in consequence, there is an important need for data-cleaning tools to detect and remove, if possible, inconsistencies in large data sets. This work proposes strategies to support data cleaning of spatial databases with respect to a set of integrity constraints that impose topological relations between spatial objects. The basic idea is to rank the geometries in a spatial data set that should be modified to improve the quality of the data (in terms of consistency). An experimental evaluation validates the proposal and shows that the order in which geometries are modified affects both the overall quality of the database and the final number of geometries to be processed to restore consistency.

An inconsistency measure can be used to compare the quality of different data sets and to quantify the cost of data cleaning. In traditional relational databases, inconsistency is defined in terms of constraints that use comparison operators between attributes. Inconsistency measures for traditional databases cannot be applied to spatial data sets because spatial objects are complex and the constraints are typically defined using spatial relations. This paper proposes an inconsistency measure to evaluate how dirty a spatial data set is with respect to a set of integrity constraints that define the topological relations that should hold between objects in the data set. The paper starts by reviewing different approaches to quantify the degree of inconsistency and showing that they are not suitable for the problem. Then, the inconsistency measure of a data set is defined in terms of the degree in which each spatial object in the data set violates topological constraints, and the possible representations of spatial objects are points, curves, and surfaces. Finally, an experimental evaluation demonstrates the applicability of the proposed inconsistency measure and compares it with previously existing approaches.

The List-Update Problem is a well studied online problem with direct applications in data compression. Although the model proposed by Sleator & Tarjan has become the standard in the field for the problem, its applicability in some domains, and in particular for compression purposes, has been questioned. In this paper, we focus on two alternative models for the problem that arguably have more practical significance than the standard model. We provide new algorithms for these models, and show that these algorithms outperform all classical algorithms under the discussed models. This is done via an empirical study of the performance of these algorithms on the reference data set for the list-update problem. The presented algorithms make use of the context-based strategies for compression, which have not been considered before in the context of the list-update problem and lead to improved compression algorithms. In addition, we study the adaptability of these algorithms to different measures of locality of reference and compressibility.

Let X = x1, x2,.... xnbe a sequence of non-decreasing integer values. Storing a compressed representation of X that supports access and search is a problem that occurs in many domains. The most common solution to this problem encodes the differences between consecutive elements in the sequence, and includes additional information (samples) to support efficient searching on the encoded values. We introduce a completely different alternative that achieves compression by encoding the differences in a search tree. Our proposal has many applications such as the representation of posting lists, geographic data, sparse bitmaps, and compressed suffix arrays, to name just a few. The structure is practical and we provide an experimental comparison to show that it is also competitive with the existing techniques.

We present in this paper a web-based version of a scrabble game, describing its architecture and some implementation details. This architecture makes possible a high degree of interactivity, so that the players perceive the game as being played in real-time. Furthermore, no client-side plug-in or applet issued. These properties are achieved by means of a carefully designed architecture that uses AJAX (Asynchronous JavaScript and XMLXML) for data exchange. This architecture guarantees low load on the server, so complex computations relative to the game logic can be done in real-time. Moreover, data structures and algorithms were designed to efficiently access a custom Galician dictionary, which supports the game functionalities. We show in this paper how this data structures and algorithms provide an efficient method to create a Scrabble move generation algorithm. We also show how the combination of these with the architecture proposed provides a fully interactive Web application that can handle complex calculations over a very large lexicon with real-time appearance.