Spatial data play an important role in many applications built over knowledge graphs, and are frequently referenced in queries posed to public query services, such as that of Wikidata.Querying for spatial data presents a significant challenge, as topological relations such as adjacent or contains imply inferred information, such as through the transitivity of the containment relation.However, despite all the recent advances in querying knowledge graphs, we still lack techniques specifically tailored for topological information.Applications looking to incorporate topological relations must either materialize the inferred relations, incurring high space and maintenance overheads, or query them with less efficient recursive algorithms, incurring high runtime overheads.In this paper we address the problem of leveraging topological information in knowledge graphs by designing efficient algorithms to process these queries.Our solution involves building a specific index that stores the topological information in a convenient compact form, and includes specialized algorithms that infer every possible relation from the basic topological facts in the graph.We show that, while using essentially the same space required to solve standard graph pattern queries, we can incorporate topological predicates, accounting for all the inferred information, all within worst-caseoptimal time.We implement our scheme and show experimentally that it outperforms baseline solutions by a notable margin.

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.

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.

The Burrows-Wheeler Transform (BWT) has become an essential tool for compressed text indexing. Computing it efficiently and within little space is essential for the practicality of the indexes that build on it. A recent algorithm (Munro, Navarro & Nekrich, SODA 2017) computes the BWT in O(n) time using O(nlgσ) bits of space for a text of length n over an alphabet of size σ. The result is of theoretical nature and its practicality is far from obvious. In this paper we engineer their solution and show that, while a basic implementation is slow in practice, the algorithm is amenable to parallelization. For a wide range of alphabet sizes, our resulting implementation outperforms all the compact constructions in the space/time tradeoff map. On the smallest alphabets we are outperformed in time, but nevertheless achieve the least space within reasonable time. For example, in DNA sequences, the most widely used application of BWTs, our construction uses 4.84 bits per base and builds the BWT at a rate of 2.13 megabases per second, whereas the closest previous alternative uses around 7.09 bits per base and runs at 4.17 megabases per second.

Given a string of length n that is composed of r runs of letters from the alphabet {0,1,...,σ-1} such that 2 ≤ σ ≤ r, we describe a data structure that, provided r ≤ n/logω(1)n, stores the string in r\log nσ/r + o(r log nσ/r) bits and supports select and access queries in O(log log(n/r)/loglogn) time and rank queries in O(log log(nσ/r)/log\logn) time. We show that r log n(σ-1)/r - O(log n/r) bits are necessary for any such data structure and, thus, our solution is succinct. We also describe a data structure that uses (1 + ε)r log nσ/r + O(r) bits, where ε > 0 is an arbitrary constant, with the same query times but without the restriction r ≤ n / logω(1)n. By simple reductions to the colored predecessor problem, we show that the query times are optimal in the important case r ≥ 2logδ n, for an arbitrary constant δ > 0. We implement our solution and compare it with the state of the art, showing that the closest competitors consume 31-46% more space.