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.

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.

We present RODGEN, an interactive, graphical user interface for generating road networks that adopts the growth-based model. The first step in the generation process is to construct the backbone of the network by either choosing between a grid-based and a ring-based predefined topology or allowing the users to define a custom one. The backbone divides the space into a number of areas, called neighborhoods. The user can populate neighborhoods either by importing existing road networks or adding roads by hand. Besides generating road networks, our interface also provides a platform for analysis. For this purpose, we employ a general-purpose graph analytics library, which allows the users to compute graph statistics, perform connectivity analysis and execute basic routing tasks.

Evacuation planning is a critical task in disaster management. Especially in situations such as natural disasters or terrorist attacks, large crowds need to move away from danger and reach designated safe zones. For this purpose, various approaches that efficiently compute evacuation plans in urban areas have been proposed. To evaluate the computed plans, previous works employ heuristics that can only roughly estimate the egress time of each plan. Intuitively, a much better approach is to estimate the egress time via simulation. However, designing a simulation model is usually a time-consuming task and, what is more, this model can only be used to evaluate evacuation plans for a specific area. In this paper, we address these issues presenting EURASIM. Our system enables the automated generation of simulation models for urban areas. Furthermore, EURASIM is designed in a way that algorithms for evacuation planning can be easily integrated, thus functioning as a testbed for the development of even better solutions.

Computing the shortest path in a road network is a fundamental problem that has attracted lots of attention. However, in many real-world scenarios, determining solely the shortest path is not enough as users want to have additional, alternative ways of reaching their destination. In this paper, we investigate a novel variant of alternative routing, termed the k-Most Diverse Near-Shortest Paths (kMDNSP). In contrast to previous work, kMDNSP aims at maximizing the diversity of the recommended paths, while bounding their length based on a user-defined constraint. Our theoretical analysis proves the NP-hardness of the problem at hand. To compute an exact solution to kMDNSP, we present an algorithm which iterates over all paths that abide by the length constraint and generates k-subsets of them as candidate results. Furthermore, in order to achieve scalability, we also design three heuristic algorithms that trade the diversity of the result for performance. Our experimental analysis compares all proposed algorithms in terms of their runtime and the quality of the recommended paths.

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.

This demonstration paper focuses on transportation-related queries within a city that go beyond simple routing and that are of interest to different types of users. For instance, individual users could be interested in which modes of transport are more effective to reach a set of alternative locations at a given time of the day, whereas urban planners could be interested in the effect that adding/removing a bus line would have in connecting regions of a city, e.g., a residential neighborhood and downtown. Given that context and using real data from the city of Berlin, we introduce RRAMEN, an interactive tool which is well equipped to support different city-scale mobility-related queries by different types of users.

Abstract In this paper, we investigate the computation of alternative paths between two locations in a road network. More specifically, we study the k-shortest paths with limited overlap ( $$k\text {SPwLO}$$ k SPwLO ) problem that aims at finding a set of k paths such that all paths are sufficiently dissimilar to each other and as short as possible. To compute $$k\text {SPwLO}$$ k SPwLO queries, we propose two exact algorithms, termed OnePass and MultiPass , and we formally prove that MultiPass is optimal in terms of complexity. We also study two classes of heuristic algorithms: (a) performance-oriented heuristic algorithms that trade shortness for performance, i.e., they reduce query processing time, but do not guarantee that the length of each subsequent result is minimum; and (b) completeness-oriented heuristic algorithms that trade dissimilarity for completeness, i.e., they relax the similarity constraint to return a result that contains exactly k paths. An extensive experimental analysis on real road networks demonstrates the efficiency of our proposed solutions in terms of runtime and quality of the result.

Shortest path computation is a fundamental problem in road networks. However, in many real-world scenarios, determining solely the shortest path is not enough. In this paper, we study the problem of finding k-Dissimilar Paths with Minimum Collective Length (kDPwML), which aims at computing a set of paths from a source s to a target t such that all paths are pairwise dissimilar by at least θ and the sum of the path lengths is minimal. We introduce an exact algorithm for the kDPwML problem, which iterates over all possible s - t paths while employing two pruning techniques to reduce the prohibitively expensive computational cost. To achieve scalability we also define the much smaller set of the simple single-via paths, and we adapt two algorithms for kDPwML queries to iterate over this set. Our experimental analysis on real road networks shows that iterating over all paths is impractical, while iterating over the set of simple single-via paths can lead to scalable solutions with only a small trade-off in the quality of the results.

Shortest path computation is a fundamental problem in road networks with various applications in research and industry. However, returning only the shortest path is often not satisfying. Users might also be interested in alternative paths that are slightly longer but have other desired properties, e.g., less frequent traffic congestion. In this paper, we study alternative routing and, in particular, the k-Shortest Paths with Limited Overlap (k-SPwLO) query, which aims at computing paths that are (a) sufficiently dissimilar to each other, and (b) as short as possible. First, we propose MultiPass, an exact algorithm which traverses the network k−1 times and employs two pruning criteria to reduce the number of paths that have to be examined. To achieve better performance and scalability, we also propose two approximate algorithms that trade accuracy for efficiency. OnePass + employs the same pruning criteria as MultiPass, but traverses the network only once. Therefore, some paths might be lost that otherwise would be part of the solution. ESX computes alternative paths by incrementally removing edges from the road network and running shortest path queries on the updated network. An extensive experimental analysis on real road networks shows that: (a) MultiPass outperforms state-of-the-art exact algorithms for computing k-SPwLO queries, (b) OnePass + runs significantly faster than MultiPass and its result is close to the exact solution, and (c) ESX is faster than OnePass + (though slightly less accurate) and scales for large road networks and large values of k.

Consider a road network, and let the preferred subnet consist of the roads a driver is more acquainted to and hence tends to follow. In this paper, we study the problem of finding the most preferred path between two network nodes; we consider two variants of this problem. We first target the Most Preferred Unrestricted Path (MPUP) that has the lowest traveling time in the non-preferred subnet; this problem was introduced in the literature as identifying the safest path though safe zones. As MPUP imposes no constraints on the total traveling time, we then introduce the Most Preferred Near Shortest Path (MPNSP) that has the lowest traveling time in the non-preferred subnet among all paths which are not much slower than the shortest path. We focus on the efficient evaluation of both problems by proposing solutions with simple pre-processing steps. An extensive evaluation demonstrates the efficiency of our techniques compared to the existing method for MPUP and to the state-of-the-art on computing multi-criteria shortest paths for MPNSP.

In this paper, we present MoTrIS, a service-oriented framework which enables spatio-temporal query processing on multimodal networks that are composed of a road network and one or more schedule-based transportation networks. MoTrIS provides a remote access API, which allows for the development of applications that require the processing of routing queries on multimodal networks. We discuss the architecture of MoTrIS and we elaborate on each of its individual components. The data input module allows for the import of data from various sources into a spatial-enabled relational database. The network module builds a multimodal network by combining a road network with one or more transportation networks. The timetable module stores and queries the schedule for each transportation mode. The query processing module enables the execution of queries over the multimodal network. The visualization module exports the results into a visualizable format. Finally, we present a web application which allows users to create, modify and test advanced spatio-temporal services, and we demonstrate all the necessary steps for a user to build such a new service.

To process shortest path and distance queries on road networks, various preprocessing techniques have been proposed. State-of-the-art methods for distance queries offer superior query time but do not provide any efficient retrieval mechanism for the shortest path. In contrast, state-of-the-art methods for shortest path queries show relatively poor performance for distance queries. In this paper, we propose a Partition-based framework for Distance and Shortest Path queries (ParDiSP), which efficiently supports both types of queries. After partitioning a road network into components, ParDiSP precomputes the distances between any node in a component and the border nodes of the same component, the pair wise distances between all border nodes, and the union of the shortest paths between all border nodes. For query processing, ParDiSP runs the ALT algorithm for both distance and shortest path queries if source and target are located in the same component. Otherwise, ParDiSP answers distance queries by combining distances from exactly three precomputed distance tables. For shortest path queries, the information in the distance tables allows to identify two border nodes that are traversed by the shortest path, thereby decomposing the path into three segments which can be computed in parallel. A detailed experimental evaluation shows that ParDiSP outperforms two state-of-the-art solutions for shortest path queries and is comparable to the state-of-the-art for distance queries. For mixed query loads containing both distance and shortest path queries, ParDiSP outperforms a combination of the best methods for each query type, while its space requirements are significantly smaller.

Shortest path computation is a fundamental problem in road networks with application in various domains in research and industry. However, returning only the shortest path is often not satisfying; users are also interested in alternative paths which might be longer but have other advantages, e.g., less frequent traffic congestion. In this paper, we formally introduce the k-Shortest Paths with Limited Overlap (k-SPwLO) problem seeking to recommend k alternative paths which are (a) as short as possible and (b) sufficiently dissimilar based on a user-controlled similarity threshold. We propose two algorithms that examine the paths from a source s to a target t in increasing order of their length and progressively construct the result set. The baseline algorithm BSL builds upon a standard algorithm for computing k-Shortest Paths, followed by a filter step. The OnePass algorithm considers the overlap constraint in each expansion step while traversing the network. We evaluate the performance of both algorithms on real road networks and show that OnePass always outperforms BSL.