This paper addresses short-term Collision-Risk-Aware ship route planning while utilizing a deep learning-based Vessel Collision Risk Assessment and Forecasting (VCRA/F) framework to quantify risks. Lacking a clear boundary between risky and viable routes, we propose a Pareto-optimal search for alternative routes, balancing collision risk and voyage time. Our main contribution is a novel framework that integrates VCRA/F for Pareto-optimal route queries in dynamic environments. We model maritime routes using a hexagon-based graph network on the sea. Our experiments on real-world AIS data validate the effectiveness of Skyline-VCRA/F while highlighting areas for further improvement.

The wide spread of Automatic Identification System (AIS) has motivated several maritime analytics operations. Vessel Location Forecasting (VLF) is one of the most critical operations for maritime awareness. However, accurate VLF is a challenging problem due to the complexity and dynamic nature of maritime traffic conditions. Furthermore, as privacy concerns and restrictions have grown, training data has become increasingly fragmented, resulting in dispersed databases of several isolated data silos among different organizations, which in turn decreases the quality of learning models. In this paper, we propose an efficient VLF solution based on LSTM neural networks, in two variants, namely Nautilus and FedNautilus for the centralized and the federated learning approach, respectively. We also demonstrate the superiority of the centralized approach with respect to current state of the art and discuss the advantages and disadvantages of the federated against the centralized approach.

Abstract Predictive analytics over mobility data is of great importance since it can assist an analyst to predict events, such as collisions, encounters, traffic jams, etc. A typical example is anticipated location prediction, where the goal is to predict the future location of a moving object, given a look-ahead time. What is even more challenging is to be able to accurately predict collective behavioural patterns of movement, such as co-movement patterns as well as their course over time. In this paper, we address the problem of Online Prediction of Co-movement Patterns. Furthermore, in order to be able to calculate the accuracy of our solution, we propose a co-movement pattern similarity measure, which facilitates the comparison between the predicted clusters and the actual ones. Finally, we calculate the clusters’ evolution through time (survive, split, etc.) and compare the cluster evolution predicted by our framework with the actual one. Our experimental study uses two real-world mobility datasets from the maritime and urban domain, respectively, and demonstrates the effectiveness of the proposed framework.

In this paper, we present an architecture for mobility data spaces enabling trustworthy and reliable data operations along with its main constituent parts. The architecture makes use of a data lake for scalable storage of diverse mobility data sets, on top of which separate computing and storage layers are implemented to allow independent scaling with a data operations toolbox providing all data operations. Furthermore, to cater for mobility analytics, machine learning and artificial intelligence support, an edge analytics suite is provided that encompasses distributed algorithms for mobility analytics and federated learning, thereby exploiting edge computing technologies. In turn, this is supported by a resource allocator that monitors the energy consumption of data-intensive operations and provides this information to the platform for intelligent task placement in edge devices, aiming at energy-efficient operations. As a result, an end-to-end platform is proposed that combines data services and infrastructure services towards supporting mobility application domains, such as urban and maritime.

The wide spread of the Automatic Identification System (AIS) and related tools has motivated several maritime analytics operations. One of the most critical operations for the purpose of maritime safety is the so-called Vessel Collision Risk Assessment and Forecasting (VCRA/F), with the difference between the two lying in the time horizon when the collision risk is calculated: either at current time by assessing the current collision risk (i.e., VCRA) or in the (near) future by forecasting the anticipated locations and corresponding collision risk (i.e., VCRF). Accurate VCRA/F is a difficult task, since maritime traffic can become quite volatile due to various factors, including weather conditions, vessel manoeuvres, etc. Addressing this problem by using complex models introduces a trade-off between accuracy (in terms of quality of assessment / forecasting) and responsiveness. In this paper, we propose a deep learning-based framework that discovers encountering vessels and assesses/predicts their corresponding collision risk probability, in the latter case via state-of-the-art vessel route forecasting methods. Our experimental study on a real-world AIS dataset demonstrates that the proposed framework balances the aforementioned trade-off while presenting up to 70% improvement in R2 score, with an overall accuracy of around 96% for VCRA and 77% for VCRF.

The massive-scale data generation of positioning (tracking) messages, collected by various surveillance means, has posed new challenges in the field of mobility data analytics in terms of extracting valuable knowledge out of this data. One of these challenges is online maritime awareness, where the goal is to monitor and ensure the safety of a fleet, including, among others, collision risk assessment. To address this challenge, we present VesselVision, a system that estimates, tracks, and visualizes vessels' collision risk. In particular, our system offers a unified solution that tracks vessels that are detected to be in encountering process and assess their corresponding collision risk over streaming AIS position data in an online fashion. The functionality of our system is demonstrated over popular real-world AIS datasets.

Maritime transport systems are essential to human mobility. A vital part of the maritime transport systems is the accurate vessel route forecasting (VRF). However, accurate VRF is a challenging task due to the fact that maritime traffic conditions are complex and dynamic. Machine learning (ML) methods can leverage from the ”explosion” of vessel surveillance information in order to encourage, enable deeper digitalization in the shipping industries and tackle the VRF problem. In this paper we investigate some of the most popular ML methods to address the VRF problem and we present an overview of these methods through an experimental testbed based on real vessel surveillance data. This work results in introducing baseline ML models for VRF purposes.

Within the last years the shipping industry invest-ments continue to grow to improve maritime transport systems. A vital part of the maritime transport systems is the accurate Vessel Traffic Flow Forecasting (VTFF). In this paper, we approach the VTFF problem from two different perspectives: a) indirect - as a vessel route forecasting application via employing predicted vessels locations in the future, and b) direct - as a flow sequence forecasting problem. In both strategies, machine learning methods are employed because they can leverage from the massive vessel surveillance information to enable deeper digitalization in the shipping industry. This work performs an experimental comparative study between the two approaches over a real dataset from the maritime domain.

The wide spread of Automatic Identification System (AIS) and tools based on it has motivated several maritime analytics operations. One of the most critical operations for the purpose of maritime safety is the so-called Vessel Collision Risk Assessment (VCRA). Accurate VCRA is a challenging task as maritime traffic is quite volatile, often affected by external factors, such as weather, etc. Addressing this problem by using complex models introduces a trade-off between accuracy quality and responsiveness. On the other hand, Machine Learning (ML) methods can better address this tradeoff. In this paper, we study the VCRA problem from the ML perspective, by proposing an architecture based on the Multi-Layered Perceptron (MLP) model. Our preliminary experimental study over a large-scale AIS dataset shows that the proposed methodology outperforms the kinematic equations-based approach.

The increasing use of devices with GPS capabilities has raised the need for storing and managing large amounts of spatio-temporal data, which can then be used by appropriate services and applications for extracting useful information from movement data. In parallel, it introduced the concept of multiple aspect trajectories that combine spatial, temporal, textual and social information in tandem. In order to capitalize on the social aspect of these movement data (specifically for social rankings), we formulate and address the problem of Social Spatio-Temporal-Keyword Pattern (S²KP) search over multiple aspect trajectory databases (MATDs). We propose an efficient in-DBMS k-d tree-based integrated index solution for multiple aspect trajectories that takes into account the sequential nature of trajectory data and a pattern search algorithm for this query type, implemented in Neo4j - a NoSQL graph DBMS. The overall search framework supports either an index-based spatial filtering first and then a social filtering based on social ranking and keywords, or vice versa, depending on a word frequency list. The efficacy of our proposal is demonstrated with an extensive evaluation over a real and a synthetic dataset.

In this demo paper we present ST_VISIONS, an easy-to-use Python library for interactive visualizations of spatial and spatio-temporal datasets. By automating the low-level details of the underlying visualization library (Bokeh), ST_VISIONS allows data scientists to create interactive, map-based visualizations, by writing Python code at a higher level of abstraction. Consequently, we accelerate the task of visualization from different sources, while we support interactive filtering, colorization, as well as multiple graphs, for various types of spatial and spatio-temporal data.

The massive-scale data generation of positioning (tracking) messages, collected by various surveillance means, has posed new challenges in the field of mobility data analytics in terms of extracting valuable knowledge out of this data. One of these challenges is online cluster analysis, where the goal is to unveil hidden patterns of collective behaviour from streaming trajectories, such as co-movement and co-stationary (aka anchorage) patterns. Towards this direction, in this paper, we demonstrate MaSEC (Moving and Stationary Evolving Clusters), a system that discovers valuable behavioural patterns as above. In particular, our system provides a unified solution that discovers both moving and stationary evolving clusters on streaming vessel position data in an online mode. The functionality of our system is evaluated over two real-world datasets from the maritime domain.

The advent of GPS technologies generates location data-streams and accentuates the importance of developing practical tools that can process and analyze the vast amounts of location data at a given moment in a meaningful way. Profiling the trajectory of a moving object with respect to the trajectories of its surrounding objects, for example, can elicit its mobility behaviour and analyze it in order to inform domain experts with critical knowledge in real time. For instance, clustering multiple moving objects with respect to their spatial and temporal dimension to identify co-movement patterns. In this paper, we propose a novel graph-based online co-movement pattern mining algorithm, called EvolvingClusters, which can be used to discover different collective movement behaviours (like the well-known flocks and convoys) in a unified way based on the activity of multiple concurrent objects through time and space. We evaluate EvolvingClusters using real-world and synthetic datasets from multiple mobility domains. Our study demonstrates the effectiveness of the proposed algorithm as well as its value towards a tool to profile semantically rich behaviour and with capabilities to observe and categorize multiple moving objects in real-time.

The i4sea research project provides effective and efficient big data integration, processing and analysis technologies to deliver both real-time and historical operational snapshots of fishing vessels activity in national sea areas. This paper presents the architecture of the i4sea big data platform for sea area monitoring and analysis of fishing vessels activity and demonstrates the operation of some use-case pilot scenarios.

Trajectory clustering is an important operation of knowledge discovery from mobility data. Especially nowadays, the need for performing advanced analytic operations over massively produced data, such as mobility traces, in efficient and scalable ways is imperative. However, discovering clusters of complete trajectories can overlook significant patterns that exist only for a small portion of their lifespan. In this paper, we address the problem of Distributed Subtrajectory Clustering in an efficient and highly scalable way. The problem is challenging because the subtrajectories to be clustered are not known in advance, but they need to be discovered dynamically based on adjacent subtrajectories in space and time. Towards this objective, we split the original problem to three sub-problems, namely Subtrajectory Join, Trajectory Segmentation and Clustering and Outlier Detection, and deal with each one in a distributed fashion by utilizing the MapReduce programming model. The efficiency and the effectiveness of our solution is demonstrated experimentally over a synthetic and two large real datasets from the maritime and urban domains and through comparison with two state of the art subtrajectory clustering algorithms.

We present a big data framework for the prediction of streaming trajectory data, enriched from other data sources and exploiting mined patterns of trajectories, allowing accurate long-term predictions with low latency. To meet this goal, we follow a multi-step methodology. First, we efficiently compress surveillance data in an online fashion, by constructing trajectory synopses that are spatio-temporally linked with streaming and archival data from a variety of diverse and heterogeneous data sources. The enriched stream of trajectory synopses is stored in a distributed RDF store, supporting data exploration via SPARQL queries. The enriched stream of synopses along with the raw data is consumed by trajectory prediction algorithms that exploit mined patterns from the RDF store, namely medoids of (sub-) trajectory clusters, which prolong the horizon of useful predictions. The framework is extended with offline and online interactive visual analytics tool to facilitate real world analysis in the maritime and the aviation domains.

Hot spot analysis is the problem of identifying statistically significant spatial clusters from an underlying data set. In this paper, we study the problem of hot spot analysis for massive trajectory data of moving objects, which has many real-life applications in different domains, especially in the analysis of vast repositories of historical traces of spatio-temporal data (cars, vessels, aircrafts). In order to identify hot spots, we propose an approach that relies on the Getis-Ord statistic, which has been used successfully in the past for point data. Since trajectory data is more than just a collection of individual points, we formulate the problem of trajectory hot spot analysis, using the Getis-Ord statistic. We propose a parallel and scalable algorithm for this problem, called THS, which provides an exact solution and can operate on vast-sized data sets. Moreover, we introduce an approximate algorithm (aTHS) that avoids exhaustive computation and trades-off accuracy for efficiency in a controlled manner. In essence, we provide a method that quantifies the maximum induced error in the approximation, in relation with the achieved computational savings. We develop our algorithms in Apache Spark and demonstrate the scalability and efficiency of our approach using a large, historical, real-life trajectory data set of vessels sailing in the Eastern Mediterranean for a period of three years.

In this paper, we demonstrate Hermes@Neo4j1, an extension of Neo4j graph DMBS for semantic trajectories of moving objects, on the so-called Spatio-Temporal-Keyword Pattern queries. For this purpose, our engine exploits on hybrid Spatio-Temporal- Keyword (STK) index structures, also boosted by an appropriate selectivity estimation model. Hermes@Neo4j functionality is demonstrated over synthetic and real semantic trajectory datasets.

We present an application framework that consumes streaming positions from a large fleet of flying aircrafts monitored in real time over a wide geographical area. Tailored for aviation surveillance, this online processing scheme only retains locations conveying salient mobility events along each flight, and annotates them as stop, change of speed, heading or altitude, etc. Such evolving trajectory synopses must keep in pace with the incoming raw streams so as to get incrementally annotated with minimal loss in accuracy. We also develop one-pass heuristics to eliminate inherent noise and provide reliable trajectory representations. Our prototype implementation on top of Apache Flink and Kafka has been tested against various real and synthetic datasets offering concrete evidence of its timeliness, scalability, and compression efficiency, with tolerable concessions to the quality of resulting trajectory approximations.

In this paper, we present an efficient in-DBMS framework for progressive time-aware sub-trajectory cluster analysis. In particular, we address two variants of the problem: (a) spatiotemporal sub-trajectory clustering and (b) index-based time-aware clustering at querying environment. Our approach for (a) relies on a two-phase process: a voting-and-segmentation phase followed by a sampling-and-clustering phase. Regarding (b), we organize data into partitions that correspond to groups of sub-trajectories, which are incrementally maintained in a hierarchical structure. Both approaches have been implemented in Hermes@PostgreSQL, a real Moving Object Database engine built on top of PostgreSQL, enabling users to perform progressive cluster analysis via simple SQL. The framework is also extended with a Visual Analytics (VA) tool to facilitate real world analysis.

Trajectory data analysis and mining require distance and similarity measures, and the quality of their results is directly related to those measures. Several similarity measures originally proposed for time-series were adapted to work with trajectory data, but these approaches were developed for well-behaved data that usually do not have the uncertainty and heterogeneity introduced by the sampling process to obtain trajectories. More recently, similarity measures were proposed specifically for trajectory data, but they rely on simplistic movement uncertainty representations, such as linear interpolation. In this article, we propose a new distance function, and a new similarity measure that uses an elliptical representation of trajectories, being more robust to the movement uncertainty caused by the sampling rate and the heterogeneity of this kind of data. Experiments using real data show that our proposal is more accurate and robust than related work.

S.192-197

In this paper, we propose an efficient in-DBMS solution for the problem of sub-trajectory clustering and outlier detection in large moving object datasets. The method relies on a two-phase process: a voting-and-segmentation phase that segments trajectories according to a local density criterion and trajectory similarity criteria, followed by a sampling-and-clustering phase that selects the most representative sub-trajectories to be used as seeds for the clustering process. Our proposal, called S 2 T-Clustering (for Sampling-based Sub-Trajectory Clustering) is novel since it is the first, to our knowledge, that addresses the pure spatiotemporal sub-trajectory clustering and outlier detection problem in a real-world setting (by ‘pure’ we mean that the entire spatiotemporal information of trajectories is taken into consideration). Moreover, our proposal can be efficiently registered as a database query operator in the context of extensible DBMS (namely, PostgreSQL in our current implementation). The effectiveness and the efficiency of the proposed algorithm are experimentally validated over synthetic and real-world trajectory datasets, demonstrating that S 2 T-Clustering outperforms an off-the-shelf in-DBMS solution using PostGIS by several orders of magnitude.

The preservation of privacy when publishing spatiotemporal traces of mobile humans is a field that is receiving growing attention. However, while more and more services offer personalized privacy options to their users, few trajectory anonymization algorithms are able to handle personalization effectively, without incurring unnecessary information distortion. In this paper, we study the problem of Personalized (K,�)anonymity , which builds upon the model of (k,δ)-anonymity, while allowing users to have their own individual privacy and service quality requirements. First, we propose efficient modifications to state-of-the-art (k,δ)-anonymization algorithms by introducing a novel technique built upon users’ personalized privacy settings. This way, we avoid over-anonymization and we decrease information distortion. In addition, we utilize datasetaware trajectory segmentation in order to further reduce information distortion. We also study the novel problem of

Predominant smartphone OS localization subsystems currently rely on server-side localization processes, allowing the service provider to know the location of a user at all times. In this paper, we propose an innovative algorithm for protecting users from location tracking by the localization service, without hindering the provisioning of fine-grained location updates on a continuous basis. Our proposed Temporal Vector Map (TVM) algorithm, allows a user to accurately localize by exploiting a k-Anonymity Bloom (kAB) filter and a bestNeighbors generator of camouflaged localization requests, both of which are shown to be resilient to a variety of privacy attacks. We have evaluated our framework using a real prototype developed in Android and Hadoop HBase as well as realistic Wi-Fi traces scaling-up to several GBs. Our study reveals that TVM can offer fine-grained localization in approximately four orders of magnitude less energy and number of messages than competitive approaches.

Maritime monitoring is a typical Big Data problem where hundreds of thousands of vessels across the globe transmit messages about their location, speed and other information. We have developed a system for online vessel tracking that performs, as a first step, a high-rate but accurate trajectory compression. Subsequently, the compressed trajectories are analyzed by a complex event recognition engine, promptly reporting alerts to maritime authorities. To deal with realistic maritime event patterns, we seamlessly integrated spatial and temporal reasoning for online event recognition. The system is evaluated on real data from the Greek seas.

The explosion of available positioning information associated with the inferred or user-declared semantics of the respective locations, already contributes in what is called the big data era, posing new challenges to the mobility data management and mining research community. In this paper, motivated by a series of challenges set in [11], we present a unified framework for the management and the analysis of our LifeSteps, i.e. data objects that include both (raw) trajectories and their semantic counterpart. In particular, we provide solutions for developing real-world semantic-aware Moving Object Database (MOD) and Trajectory Data Warehouse (TDW) systems and we devise respective query processing algorithms. Our experimental study on synthetic data including synchronized raw (i.e., GPS log) and semantic (i.e., diaries) information, verifies the effectiveness and efficiency of the proposed framework.

We present a system that combines intelligent online tracking with complex event recognition against streaming positions relayed from numerous vessels. Given the vital importance of maritime safety to the environment, the economy, and in national security, our sys-tem leverages the real-time acquisition of vessel activity with ge-ographical and other static information. Thus, it can offer timely notification in emergency situations, such as intrusion into marine preservation areas, loitering, and unsafe sailing. Thanks to a mobil-ity tracking module, evolving trajectories generated by massive po-sitional updates can be compressed online into concise, but reliable synopses per ship, retaining only salient motion features within a sliding window. These features are exploited by a complex event recognition module that detects suspicious situations of interest to maritime authorities. We conducted a comprehensive empirical validation against a real dataset of traces collected from thousands of vessels. Our results confirm the scalability and approximation accuracy of the proposed system, and thus demonstrate its poten-tial for effective, real-time maritime monitoring. 1.

In this paper we present an algorithm for optimal processing of time-dependent sequenced route queries in road networks, i.e., given a road network where the travel time over an edge is time-dependent and a given ordered list of categories of interest, we find the fastest route between an origin and destination that passes through a sequence of points of interest belonging to each of the specified categories of interest. Our approach uses the A* search paradigm equipped with an admissible heuristic function, thus guaranteed to yield the optimal solution, along with a pruning scheme for further reducing the search space. Our experiments using a real data set have shown our proposed solution to be up to two orders of magnitude faster than a previous solution extended to handle time-dependency.

Indoor Positioning Systems (IPS) have recently received considerable attention, mainly because GPS is unavailable in indoor spaces and consumes considerable energy. On the other hand, predominant Smartphone OS localization subsystems currently rely on server-side localization processes, allowing the service provider to know the location of a user at all times. In this paper, we propose an innovative algorithm for protecting users from location tracking by the localization service, without hindering the provisioning of fine-grained location updates on a continuous basis. Our proposed Temporal Vector Map (TVM) algorithm, allows a user to accurately localize by exploiting a k-Anonymity Bloom (kAB) filter and a bestNeighbors generator of camouflaged localization requests, both of which are shown to be resilient to a variety of privacy attacks. We have evaluated our framework using a real prototype developed in Android and Hadoop HBase as well as realistic Wi-Fi traces scaling-up to several GBs. Our analytical evaluation and experimental study reveal that TVM is not vulnerable to attacks that traditionally compromise k-anonymity protection and indicate that TVM can offer fine-grained localization in approximately four orders of magnitude less energy and number of messages than competitive approaches.

In traffic research, management, and planning a number of path-based analyses are heavily used, e.g., for computing turn-times, evaluating green waves, or studying traffic flow. These analyses require retrieving the trajectories that follow the full path being analyzed. Existing path queries cannot sufficiently support such path-based analyses because they retrieve all trajectories that touch any edge in the path. In this paper, we define and formalize the strict path query. This is a novel query type tailored to support path-based analysis, where trajectories must follow all edges in the path. To efficiently support strict path queries, we present a novel NET work-constrained TRAjectory index (NETTRA). This index enables very efficient retrieval of trajectories that follow a specific path, i.e., strict path queries. NETTRA uses a new path encoding scheme that can determine if a trajectory follows a specific path by only retrieving data from the first and last edge in the path. To correctly answer strict path queries existing network-constrained trajectory indexes must retrieve data from all edges in the path. An extensive performance study of NETTRA using a very large real-world trajectory data set, consisting of 1.7 million trajectories (941 million GPS records) and a road network with 1.3 million edges, shows a speed-up of two orders of magnitude compared to state-of-the-art trajectory indexes.

We present the INTRA system for interactive path-based traffic analysis. The analyses are developed in collaboration with traffic researchers and provide novel insights into conditions such as congestion, travel-time, choice of route, and traffic-flow. INTRA supports interactive point-and-click analysis, due to a novel and efficient indexing structure. With the web-site daisy.aau.dk/its/spqdemo/we will demonstrate several analyses, using a very large real-world data set consisting of 1.9 billion GPS records (1.5 million trajectories) recorded from more than 13 000 vehicles, and touching most of the road network in Denmark.

Mobility data sources feed larger and larger trajectory databases nowadays. Due to the need of extracting useful knowledge patterns that improve services based on users' and customers' behavior, querying and mining such databases has gained significant attention in recent years. However, publishing mobility data may lead to severe privacy violations. In this paper, we present Private-HERMES, an integrated platform for applying data mining and privacy-preserving querying over mobility data. The presented platform provides a two-dimension benchmark framework that includes: (i) a query engine that provides privacy-aware data management functionality of the in-house data via a set of auditing mechanisms that protect the sensitive information against several types of attacks, and (ii) a progressive analysis framework, which, apart from anonymization methods for data publishing, includes various well-known mobility data mining techniques to evaluate the effect of anonymization in the querying and mining results. The demonstration of Private-HERMES via a real-world case study, illustrates the flexibility and usefulness of the platform for supporting privacy-aware data analysis, as well as for providing an extensible blueprint benchmark architecture for privacy-preservation related methods in mobility data.

Moving Object Databases (MOD), although ubiquitous, still call for methods that will be able to understand, search, analyze, and browse their spatiotemporal content. In this paper, we propose a method for trajectory segmentation and sampling based on the representativeness of the (sub)trajectories in the MOD. In order to find the most representative subtrajectories, the following methodology is proposed. First, a novel global voting algorithm is performed, based on local density and trajectory similarity information. This method is applied for each segment of the trajectory, forming a local trajectory descriptor that represents line segment representativeness. The sequence of this descriptor over a trajectory gives the voting signal of the trajectory, where high values correspond to the most representative parts. Then, a novel segmentation algorithm is applied on this signal that automatically estimates the number of partitions and the partition borders, identifying homogenous partitions concerning their representativeness. Finally, a sampling method over the resulting segments yields the most representative subtrajectories in the MOD. Our experimental results in synthetic and real MOD verify the effectiveness of the proposed scheme, also in comparison with other sampling techniques.

Existing approaches for privacy-aware mobility data sharing aim at publishing an anonymized version of the mobility dataset, operating under the assumption that most of the information in the original dataset can be disclosed without causing any privacy violations. In this paper, we assume that the majority of the information that exists in the mobility dataset must remain private and the data has to stay in-house to the hosting organization. To facilitate privacy-aware sharing of the mobility data we develop a trajectory query engine that allows subscribed users to gain restricted access to the database to accomplish various analysis tasks. The proposed engine (i) audits queries for trajectory data to block potential attacks to user privacy, (ii) supports range, distance, and k-nearest neighbors spatial and spatiotemporal queries, and (iii) preserves user anonymity in answers to queries by (a) augmenting the real trajectories with a set of carefully crafted, realistic fake trajectories, and (b) ensuring that no user-specific sensitive locations are reported as part of the returned trajectories.

Technological advances in sensing technologies and wireless telecommunication devices enable novel research fields related to the management of trajectory data. As it usually happens in the data management world, the challenge after storing the data is the implementation of appropriate analytics for extracting useful knowledge. However, traditional data warehousing systems and techniques were not designed for analyzing trajectory data. Thus, in this work, we demonstrate a framework that transforms the traditional data cube model into a trajectory warehouse. As a proof-of-concept, we implemented T-WAREHOUSE, a system that incorporates all the required steps for Visual Trajectory Data Warehousing, from trajectory reconstruction and ETL processing to Visual OLAP analysis on mobility data.

The application of Data Warehousing (DW) and OLAP techniques on conventional data has been extensively studied in the literature. On the other hand, Trajectory Data Warehousing and Trajectory OLAP are relatively new research areas, which have to deal with the spatiotemporal (hence dynamic) nature of such data. In this paper, we present an innovative organization of a trajectory data cube in order to be able to answer OLAP queries considering different interpretations of the notion of trajectory. Thus, ad-hoc analysis on trajectory data cubes can be achieved, which can be really useful for a number of applications. Preliminary experimental results illustrate the applicability and efficiency of our approach.

Wireless sensor networks are becoming increasingly popular for a variety of applications. Users are frequently faced with the surprising discovery that readings produced by the sensing elements of their motes are often contaminated with outliers. Outlier readings can severely affect applications that rely on timely and reliable sensory data in order to provide the desired functionality. As a consequence, there is a recent trend to explore how techniques that identify outlier values can be applied to sensory data cleaning. Unfortunately, most of these approaches incur an overwhelming communication overhead, which limits their practicality. In this paper we introduce an in-network outlier detection framework, based on locality sensitive hashing, extended with a novel boosting process as well as efficient load balancing and comparison pruning mechanisms. Our method trades off bandwidth for accuracy in a straightforward manner and supports many intuitive similarity metrics.

A flood of data pertinent to moving objects is available today, and will be more in the near future, particularly due to the automated collection of privacy-sensitive telecom data from mobile phones and other location-aware devices. Such wealth of data, referenced both in space and time, may enable novel classes of applications of high societal and economic impact, provided that the discovery of consumable and concise knowledge out of these raw data is made possible. Recent research activities have developed theory, techniques and systems for geographic knowledge discovery and delivery, some of them based on privacy-preserving methods for extracting knowledge from large amounts of raw data referenced in space and time. All these efforts aim at devising knowledge discovery and analysis methods for trajectories of moving objects.The fundamental hypothesis is that it is possible, in principle, to aid citizens in their mobile activities by analysing the traces of their past activities by means of data mining techniques. For instance, behavioural patterns derived from mobile trajectories may allow inducing traffic flow information, capable to help people travel efficiently, to help public administrations in traffic-related decision making for sustainable mobility and security management, as well as to help mobile operators in optimising bandwidth and power allocation on the network. On the other hand, it is clear that the use of personal sensitive data arouses concerns about citizen's privacy rights.In this tutorial, we establish a framework for the challenges and the mining solutions for the geographic information collected by Moving Object Database (MOD) engines. We first discuss the challenges of collecting mobility data, and elaborate on the impact of trajectory data analysis in several modern applications. We then discuss methodologies and techniques to collect raw data, reconstruct trajectory information, and efficiently store it in MODs. We continue with an overview of knowledge discovery approaches for movement data. Finally, we propose a research agenda and identify areas where interdisciplinary studies are needed.

Mining trajectory databases (TD) has gained great interest due to the popularity of tracking devices. On the other hand, the inherent presence of uncertainty in TD (e.g., due to GPS errors) has not been taken yet into account during the mining process. In this paper, we study the effect of uncertainty in TD clustering and introduce a three-step approach to deal with it. First, we propose an intuitionistic point vector representation of trajectories that encompasses the underlying uncertainty and introduce an effective distance metric to cope with uncertainty. Second, we devise CenTra, a novel algorithm which tackles the problem of discovering the centroid trajectory of a group of movements. Third, we propose a variant of the fuzzy C-means (FCM) clustering algorithm, which embodies CenTra at its update procedure. The experimental evaluation over real world TD demonstrates the efficiency and effectiveness of our approach.

An emerging topic in the field of spatial data management is the handling of location uncertainty of spatial objects, mainly due to inaccurate measurements. The literature on location uncertainty so far has focused on modifying traditional spatial search algorithms in order to handle the impact of objects' location uncertainty in query results. In this paper, we present the first, to the best of our knowledge, theoretical analysis that estimates the average number of false hits introduced in the results of rectangular range queries in the case of data points uniformly distributed in 2D space. Then, we relax the original distribution assumptions showing how to deal with arbitrarily distributed data points and more realistic location uncertainty distributions. The accuracy of the results of our analytical approach is demonstrated through an extensive experimental study using various synthetic and real datasets. Our proposal can be directly employed in spatial database systems in order to provide users with the accuracy of spatial query results based only on known dataset and query parameters.

In this work we propose DAEDALUS, a formal framework and system, specifically focussed on progressive combination of mining and querying operators. The core component of DAEDALUS is the MO-DMQL query language that extends SQL in two respects, namely a pattern definition operator and the capability to uniform manipulating both raw data and unveiled patterns. DAEDALUS system is specifically focussed on movement data and has been implemented as a query execution layer on top of the Hermes Moving Object Database. The expressiveness and usefulness of the MODMQL language as well as the computational capabilities of DAEDALUS are qualitatively evaluated by means of a case study.

This demo presents Pattern-Miner, an integrated environment for pattern management and mining that deals with the whole lifecycle of patterns, from their generation (using data mining techniques) to their storage and querying, putting also emphasis on the comparison between patterns and meta-mining operations over the extracted patterns. Pattern comparison (comparing results of the data mining process) and meta-mining are high level pattern operations that can be applied in a variety of applications, from database change management to image comparison and retrieval.

Decision trees are among the most popular pattern types in data mining due to their intuitive representation. However, little attention has been given on the definition of measures of semantic similarity between decision trees. In this work, we present a general framework for similarity estimation that includes as special cases the estimation of semantic similarity between decision trees, as well as various forms of similarity estimation on classification datasets with respect to different probability distributions defined over the attribute-class space of the datasets. The similarity estimation is based on the partitions induced by the decision trees on the attribute space of the datasets. We use the proposed framework in order to estimate the semantic similarity of decision trees induced from different subsamples of classification datasets; we evaluate its performance with respect to the empirical semantic similarity, which we estimate on the basis of independent hold-out test sets. The availability of similarity measures on decision trees opens a wide range of possibilities for meta-analysis and meta-mining of the data mining results.

We present HERMES, a prototype system based on a powerful query language for trajectory databases, which enables the support of aggregative Location-Based Services (LBS). The key observation that motivates HERMES is that the more the knowledge in hand about the trajectory of a mobile user, the better the exploitation of the advances in spatio-temporal query processing for providing intelligent LBS. HERMES is fully incorporated into a state-of-the-art Object-Relational DBMS, and its demonstration illustrates its flexibility and usefulness for delivering custom-defined LBS.

The problem of trajectory similarity in moving object databases is a relatively new topic in the spatial and spatiotemporal database literature. Existing work focuses on the spatial notion of similarity ignoring the temporal dimension of trajectories and disregarding the presence of a general-purpose spatiotemporal index. In this work, we address the issue of spatiotemporal trajectory similarity search by defining a similarity metric, proposing an efficient approximation method to reduce its calculation cost, and developing novel metrics and heuristics to support k-most-similar-trajectory search in spatiotemporal databases exploiting on existing R-tree-like structures that are already found there to support more traditional queries. Our experimental study, based on real and synthetic datasets, verifies that the proposed similarity metric efficiently retrieves spatiotemporally similar trajectories in cases where related work fails, while at the same time the proposed algorithm is shown to be efficient and highly scalable.

In this paper we introduce the problem of Constrained Subspace Skyline Queries. This class of queries can be thought of as a generalization of subspace skyline queries using range constraints. Although both constrained skyline queries and subspace skyline queries have been addressed previously, the implications of constrained subspace skyline queries has not been examined so far. Constrained skyline queries are usually more expensive than regular skylines. In case of constrained subspace skyline queries additional performance degradation is caused through the projection. In order to support constrained skylines for arbitrary subspaces, we present approaches exploiting multiple low-dimensional indexes instead of relying on a single high-dimensional index. Effective pruning strategies are applied to discard points from dominated regions. An important ingredient of our approach is the workload-adaptive strategy for determining the number of indexes and the assignment of dimensions to the indexes. Extensive performance evaluation shows the superiority of our proposed technique compared to its most related competitors.

There is much recent work on detecting and tracking change in clusters, often based on the study of the spatiotemporal properties of a cluster. For the many applications where cluster change is relevant, among them customer relationship management, fraud detection and marketing, it is also necessary to provide insights about the nature of cluster change: Is a cluster corresponding to a group of customers simply disappearing or are its members migrating to other clusters? Is a new emerging cluster reflecting a new target group of customers or does it rather consist of existing customers whose preferences shift? To answer such questions, we propose the framework MONIC for modeling and tracking of cluster transitions. Our cluster transition model encompasses changes that involve more than one cluster, thus allowing for insights on cluster change in the whole clustering. Our transition tracking mechanism is not based on the topological properties of clusters, which are only available for some types of clustering, but on the contents of the underlying data stream. We present our first results on monitoring cluster transitions over the ACM digital library.

In this paper we describe a new density-biased sampling algorithm. It exploits spatial indexes and the local density information they preserve, to provide improved quality of sampling result and fast access to elements of the dataset. It attains improved sampling quality, with respect to factors like skew, noise or dimensionality. Moreover, it has the advantage of efficiently handling dynamic updates, and it requires low execution times. The performance of the proposed method is examined experimentally. The comparative results illustrate its superiority over existing methods.

This paper addresses the problem of finding the K closest pairs between two spatial data sets, where each set is stored in a structure belonging in the R-tree family. Five different algorithms (four recursive and one iterative) are presented for solving this problem. The case of 1 closest pair is treated as a special case. An extensive study, based on experiments performed with synthetic as well as with real point data sets, is presented. A wide range of values for the basic parameters affecting the performance of the algorithms, especially the effect of overlap between the two data sets, is explored. Moreover, an algorithmic as well as an experimental comparison with existing incremental algorithms addressing the same problem is presented. In most settings, the new algorithms proposed clearly outperform the existing ones.

Selection and join queries are fundamental operations in database management systems (DBMS). Support for nontraditional data, including spatial objects, in an efficient manner is of ongoing interest in database research. Toward this goal, access methods and cost models for spatial queries are necessary tools for spatial query processing and optimization. We present analytical models that estimate the cost (in terms of node and disk accesses) of selection and join queries using R-tree-based structures. The proposed formulae need no knowledge of the underlying R-tree structure(s) and are applicable to uniform-like and nonuniform data distributions. In addition, experimental results are presented which show the accuracy of the analytical estimations when compared to actual runs on both synthetic and real data sets.

One of the most important types of query processing in spatial databases and geographic information systems is the spatial join, an operation that selects, from two relations, all object pairs satisfying some spatial predicate.A multiway join combines data originated from more than two relations.Although several techniques have been proposed for pairwise spatial joins, only limited work has focused on multiway spatial join processing.This paper solves multiway spatial joins by applying systematic search algorithms that exploit R-trees to efficiently guide search, without building temporary indexes or materializing intermediate results.In addition to general methodologies, we propose cost models and an optimization algorithm, and evaluate them through extensive experimentation.

The join query is one of the fundamental operations in database management systems (DBMSs). Modern DBMSs should be able to support non traditional data, including spatial objects, in an efficient manner. Towards this goal, spatial data structures can be adopted in order to support the execution of join queries on sets of multidimensional data. The paper introduces analytical models that estimate the cost (in terms of node or disk accesses) of join queries involving two multidimensional indexed data sets using R tree based structures. In addition, experimental results are presented, which show the accuracy of the analytical estimations when compared to actual runs on both synthetic and real data sets. It turns out that the relative error rarely exceeds 15% for all combinations, a fact that makes the proposed cost models useful tools for efficient spatial query optimization.

A new issue that arises in modern applications involves the efficient manipulation of (static or moving) spatial objects, and the relationships among them. As a result, modern database systems should be able to efficiently support that type of data. Towards this goal, appropriate extensions of multidimensional access methods can be exploited in order to index and retrieve spatiotemporal objects, satisfying users' demands. This paper introduces the basic specifications such a spatiotemporal index structure should follow, evaluates existing proposals with respect to the above specifications, and illustrates issues of interest involving object representation, query processing, and index maintenance.

Spatial relations are important in numerous domains, such as Spatial Query Languages, Image and Multimedia Databases, Reasoning and Geographic Applications. This paper is concerned with the retrieval of topological and direction relations using spatial data structures based on Minimum Bounding Rectangles. We describe topological and direction relations between region objects and we study the spatial information that Minimum Bounding Rectangles convey about the actual objects they enclose. Then we apply the results in R-trees and their variations, R-trees and R*-trees, in order to minimize the number of disk accesses for queries involving topological and direction relations. We also investigate queries that express complex conditions in the form of disjunctions and conjunctions, and discuss possible extensions.

The use of Spatial Access Methods (SAMs) in spatial database systems, such as Geographical Information Systems, is necessary to achieve efficient retrieval of data items according to their spatial properties. Existing SAMs organizing minimum bounding rectangle (MBR) approximations of spatial objects can be classified into four groups. Each group is characterized by the special technique adopted for managing MBRs: (a) Ordering, (b) Transformation, (c) Clipping, and (d) Overlapping. This paper introduces a new technique. The basic idea of this technique is to represent all spatial objects by their MBRs and further reduce them into points of the same dimensionality, so that any multidimensional Point Access Method (PAM) may be used to support access. Essential for the functionality of the new method is the query window extension. The results of both analytical and experimental work show that SAMs using the new technique clearly outperform popular SAMs, such as the R- and R*-trees for data sets consisting of equal-sized MBRs. As for data sets of varying MBR sizes a competitive performance can be obtained.

In this paper we present an analytical model that predicts the performance of R-trees (and its variants) when a range query needs to be answered.The cost model uses knowledge of the dataset only, i.e., the proposed formula that estimates the number of disk accesses is a hmction of data properties, namely, the amount of data and their density in the work space.In other words, the proposed model is applicable even before the construction of the R-tree index, a fact that makes it a useful tool for dynamic spatial databases.Several experiments on synthetic and real datasets show that the proposed analytical model is very accurate, the relative error being usually around 10%-15%, for uniform and non-uniform distributions.We believe that this error is involved with the gap between efficient R-tree variants, like the R*-tree, and an optimum, not implemented yet, method.Our work extends previous research concerning R-tree analysis and constitutes a useful tool for spatial query optimizers that need to evaluate the cost of a complex spatial query and its execution procedure.

Recent developments in spatial relations have led to their use in numerous applications involving spatial databases. This paper is concerned with the retrieval of topological relations in Minimum Bounding Rectangle-based data structures. We study the topological information that Minimum Bounding Rectangles convey about the actual objects they enclose, using the concept of projections. Then we apply the results to R-trees and their variations, R+-trees and R*-trees in order to minimise disk accesses for queries involving topological relations. We also investigate queries that involve complex spatial conditions in the form of disjunctions and conjunctions and we discuss possible extensions.