With recent sensor and tracking technology advances, the volume of available trajectory data is steadily increasing. Consequently, managing and analyzing trajectory data has seen significant interest from the research community. The challenges presented by trajectory data arise from their spatio-temporal nature as well as the uncertainty regarding locations between sampled points. In this paper, we present a formal spatio-temporal predicate logic with configurable strictness parameters and two novel operators: (1) a spatio-temporal selection operator for filtering trajectories, and (2) a spatio-temporal crop operator for extracting relevant sub-trajectories based on spatio-temporal predicates. Furthermore, we integrate a similarity-based join operators for flexible trajectory comparison. Finally, we show that our predicate logic is expressive enough to capture all spatial and temporal relations put forward by previous work.

Trajectory clustering is one of the most important data mining tasks on this spatio-temporal data type. Many existing algorithms perform clustering by employing a distance measure designed specifically for trajectory data. However, compared to the clustering of n-dimensional points, the choice of a suitable distance measure for trajectory data is not straightforward. In this work, we conduct an experimental evaluation to examine the efficacy of different trajectory distance measures in relation to different data sets and different clustering algorithms. Our experiments show noticeable trends in the distribution of distance measure performance, dependent on clustering method and data set characteristics.

Abstract Highways play a crucial role in transportation services as they facilitate long-distance traveling and allow driving at an almost constant speed, thus resulting in lower fuel consumption and emissions. Many existing highway systems were designed before practical computational tools had been developed. Furthermore, most existing approaches to evaluating highways focus on analyzing mobility data rather than studying the design of the highway system. To address this gap in existing research, in this paper, we investigate the problem of evaluating the efficacy of the design of real-world highway systems. To this end, we propose two novel measures for the effectiveness of highway systems, along with both exact and heuristic algorithms to compute them. In addition, we present a first-cut heuristic algorithm that aims to compute a highway system that optimizes our proposed measures. In our experiments, we demonstrate the potential of our methods in measuring the efficacy of real-world highway systems. We also evaluate the performance of our heuristic algorithm in computing a rough design of an efficient highway system.

Cardinality estimation is a central task of cost-based database query optimization. Accurate estimates enable optimizers to identify and avoid expensive plans requiring large intermediate results. While cardinality estimation has been studied extensively in relational databases, research in the setting of graph databases has been more scarce. Furthermore, recent studies have shown that machine-learning-based methods can be utilized for cardinality estimation in both relational and graph databases. In this paper, we focus on the problem of estimating the cardinality of path patterns in graph databases, and we propose the Sequence-based Path Pattern Cardinality Estimator (SPACE). Our approach treats path patterns as sequences of node labels and edge types and assign similar cardinalities to path patterns with similar node and edge order. SPACE uses a dual approach: it encodes the sequence of nodes and edges to capture structural characteristics of the path pattern, while also incorporating a cardinality-based encoding to integrate cardinality information throughout learning. In a comprehensive experimental evaluation, we show that our method outperforms the state of the art in terms of both accuracy ( Q -error) and training time.

Cardinality estimation is an important step in cost-based database query optimization. The accuracy of the estimates directly affects the ability of an optimizer to identify the most efficient query execution plan correctly. In this paper, we study cardinality estimation of LIKE-queries, i.e., queries that use the LIKE-operator to match a pattern with wildcards against string-valued attributes. While both traditional and machine-learning-based approaches have been proposed to tackle this problem, we argue that they all suffer from drawbacks. Most importantly, many state-of-the-art approaches are not designed for patterns that contain wildcards in-between characters. Based on past research on neural language models, we introduce the LIKE-Pattern Language Model (LPLM) that uses a new language and a novel probability distribution function to capture the semantics of general LIKE-patterns. We also propose a method to generate training data for our model. We demonstrate that our method outperforms state-of-the-art approaches in terms of precision (Q-error), while offering comparable runtime performance and memory requirements.

Highways play a crucial role in transportation services as they facilitate long-distance traveling and allow driving at an almost constant speed, thus resulting in lower fuel consumption and emissions. Many existing highway systems were designed before practical computational tools had been developed. Furthermore, most existing approaches to evaluating highways focus on analyzing mobility data rather than studying the design of the highway system. To address this gap in existing research, in this paper, we study the problem of evaluating the efficacy of the design of real-world highway systems. To this end, we propose two novel measures for the efficacy of highway systems, along with algorithms to compute them. In addition, we present a first-cut heuristic algorithm that aims at computing a highway system that optimizes our proposed measures. In our experiments, we demonstrate the potential of our methods in measuring the efficacy of real-world highway systems. We also evaluate the performance of our heuristic algorithm in computing a rough design of an efficient highway system.

In database systems, accurate cardinality estimation is a cornerstone of effective query optimization. In this context, estimators that use machine learning have shown significant promise. Despite their potential, the effectiveness of these learned estimators strongly depends on their ability to learn from small training sets. This paper presents a novel approach for learned cardinality estimation that addresses this issue by enhancing sample efficiency. We propose a neural network architecture informed by geometric deep learning principles that represents queries as join graphs. Furthermore, we introduce an innovative encoding for complex predicates, treating their encoding as a feature selection problem. Additionally, we devise a regularization term that employs equalities of the relational algebra and three-valued logic, augmenting the training process without requiring additional ground truth cardinalities. We rigorously evaluate our model across multiple benchmarks, examining q-errors, runtimes, and the impact of workload distribution shifts. Our results demonstrate that our model significantly improves the end-to-end runtimes of PostgreSQL, even with cardinalities gathered from as little as 100 query executions.

The availability of GPS sensors in vehicles has enabled the collection of trajectory data that can be utilized to improve the quality of location-based services. However, mostly due to privacy concerns, many data sets are published without containing entire trajectories but only the source location, the target location and the duration of recorded trips. In this paper, we study the problem of route recovery from trip data. In contrast to recent works that assume the availability of entire trajectories for past trips, we investigate methods for route recovery in the absence of such historical data, and we present methods for recovering the single most likely route that a vehicle has travelled. Furthermore, we introduce the region recovery problem that aims at determining a small region that is very likely to contain the traveled route. We also introduce region recovery methods for both single trips and trip groups. In a comprehensive experimental evaluation, we study the efficacy of our solutions for both the route and the region recovery problem. For the region recovery problem in particular, we demonstrate the pros and cons of each method along with the trade-off they offer between the size of the recovered region and the likelihood that the region contains the actual route.

Processing shortest path queries is a basic operation in many graph problems. Both preprocessing-based and batch processing techniques have been proposed to speed up the computation of a single shortest path by amortizing its costs. However, both of these approaches suffer from limitations. The former techniques are prohibitively expensive in situations where the precomputed information needs to be updated frequently due to changes in the graph, while the latter require coordinates and cannot be used on non-spatial graphs. In this paper, we address both limitations and propose novel techniques for batch processing shortest paths queries using landmarks. We show how preprocessing can be avoided entirely by integrating the computation of landmark distances into query processing. Our experimental results demonstrate that our techniques outperform the state of the art on both spatial and non-spatial graphs with a maximum speedup of 3.61 × in online scenarios.

The quality of query execution plans in database systems determines how fast a query can be executed. It has been shown that conventional query optimization still selects sub-optimal or even bad execution plans, due to errors in the cardinality estimation. Although cardinality estimation errors are an evident problem, they are in general not considered in the selection of query execution plans. In this paper, we present three novel metrics for the robustness of relational query execution plans w.r.t. cardinality estimation errors. We also present a novel plan selection strategy that takes both, estimated cost and estimated robustness into account, when choosing a plan for execution. Finally, we share the results of our experimental comparison between robust and conventional plan selection on real world and synthetic benchmarks, showing a speedup of at most factor 3.49.

A key promise of SQL is that the optimizer will find the most efficient execution plan, regardless of how the query is formulated. In general, query optimizers of modern database systems are able to keep this promise, with the notable exception of nested queries. While several optimization techniques for nested queries have been proposed, their adoption in practice has been limited. In this paper, we argue that the NF2 (non-first normal form) algebra, which was originally designed to process nested tables, is a better approach to nested query optimization as it fulfills two key requirements. First, the NF2 algebra can represent all types of nested queries as well as both existing and novel optimization techniques based on its equivalences. Second, performance benefits can be achieved with little changes to existing transformation-based query optimizers as the NF2 algebra is an extension of the relational algebra.

In order to manage XML documents, native XML databases use specific encodings that map the hierarchical structure of a document to a flat representation. Several encodings have been proposed that differ in terms of their support for certain query workloads. While some encodings are optimized for query processing, others focus on data manipulation. For example, the Pre/Dist/Size XML encoding has been designed to support queries over all XPath axes efficiently, but processing atomic updates in XML documents can be costly. In this paper, we present a technique, so-called structural bulk updates, that works in concert with the XQuery Update Facility to support efficient updates on the Pre/Dist/Size encoding. We demonstrate the benefits of our technique in a detailed performance evaluation based on the XMark benchmark.

Continuous SPARQL (C-SPARQL) is proposed as new language for continuous queries over streams of RDF data. It covers a gap in the Semantic Web abstractions which is needed for many emerging applications, including our focus on Urban Computing. In this domain, sensor-based information on roads must be processed to deduce localized traffic conditions and then produce traffic management strategies. Executing C-SPARQL queries requires the effective integration of SPARQL and streaming technologies, which capitalize over a decade of research and development; such integration poses several nontrivial challenges.

C-SPARQL is an extension of SPARQL to support continuous queries, registered and continuously executed over RDF data streams, considering windows of such streams. Supporting streams in RDF format guarantees interoperability and opens up important applications, in which reasoners can deal with knowledge that evolves over time. We present C-SPARQL by means of examples in Urban Computing.

In most web mashup applications, the content is generated using either web feeds or an application programming interface (API) based on web services. Both approaches have limitations. Data models provided by web feeds are not powerful enough to permit complex data structures to be transmitted. APIs based on web services are usually different for each web application, and thus different implementations of the APIs are required for each web service that a web mashup application uses. We propose a database-driven approach to web mashups that supports integration at the database level and enables mashup developers to work with a uniform abstract model and have direct access to powerful features of database systems. We describe how we have implemented this approach based on an object-oriented database system with a rich object model and a generic proxy mechanism for data integration and synchronisation.

Our demonstration is a paper-based interactive guide for visitors to the world's largest international arts festival that was developed as part of a project investigating new forms of context-aware information delivery and interaction in mobile environments. Information stored in a database is accessed from a set of interactive paper documents, including a printed festival brochure, a city map and a bookmark. Active areas are defined within the documents and selection of these using a special digital pen causes the corresponding query request along with context data to be sent to a festival application database and the response is returned to the visitor in the form of generated speech output. In addition to paper-based information browsing and transactions such as ticket booking, the digital pen can also be applied for data capture of event ratings and handwritten comments on events. The system integrates three main database components - a cross-media information platform, a content management framework for multi-channel context-aware publishing of data and the festival application database.