Due to the limited driving range, insufficient charging facilities, and time-consuming recharging, optimizing charging routes for electric vehicles (EVs) presents unique challenges compared to conventional vehicles. The time and location of EV charging during a trip not only affect an individual EV’s travel time but also influence others, as queues may form at charging station(s). This issue is at large seen as a significant constraint for uplifting EV sales in many countries. In this study, we introduce a novel EV Route Planning problem, which involves two parts: (i) finding the fastest route with recharging for an EV routing request. We model the problem as a new graph problem and prove its NP-hardness. We propose an innovative two-phase algorithm that efficiently traverses the graph to identify the optimal charging route for each EV. (ii) We find routes with minimized travel time for an EV while strategically avoid charging stations and time to recharge at those stations which can lead to minimized travel time for upcoming EVs. For this purpose, we introduce the concept of an “influence factor” to guide heuristic decisions. Our results demonstrate that this method reduces total travel time by 50% compared to the state-of-the-art on real-world datasets, with benefits becoming more significant as the number of EVs on the road increases.

The rapid growth of online retail and e-commerce has made effective and efficient Vehicle Routing Problem (VRP) solutions essential. To meet rising demand, companies are adding more depots, which changes the VRP problem to a complex optimization task of Multi-Depot VRP (MDVRP) where the routing decisions of vehicles from multiple depots are highly interdependent. The complexities render traditional VRP methods suboptimal and non-scalable for the MDVRP. In this paper, we propose a novel approach to solve MDVRP addressing these interdependencies, hence achieving more effective results. The key idea is, the MDVRP can be broken down into two core spatial tasks: assigning customers to depots and optimizing the sequence of customer visits. We adopt task-decoupling approach and propose a two-stage framework that is scalable: (i) an interdependent partitioning module that embeds spatial and tour context directly into the representation space to globally match customers to depots and assign them to tours; and (ii) an independent routing module that determines the optimal visit sequence within each tour. Extensive experiments on both synthetic and real-world datasets demonstrate that our method outperforms all baselines across varying problem sizes, including the adaptations of learning-based solutions for single-depot VRP. Its adaptability and performance make it a practical and readily deployable solution for real-world logistics challenges.

The increasing availability of urban data offers new opportunities for learning region representations, which can be used as input to machine learning models for downstream tasks such as check-in or crime prediction. While existing solutions have produced promising results, an issue is their fixed formation of regions and fixed input region features, which may not suit the needs of different downstream tasks. To address this limitation, we propose a model named FlexiReg for urban region representation learning that is flexible with both the formation of urban regions and the input region features. FlexiReg is based on a spatial grid partitioning over the spatial area of interest. It learns representations for the grid cells, leveraging publicly accessible data, including POI, land use, satellite imagery, and street view imagery. We propose adaptive aggregation to fuse the cell representations and prompt learning techniques to tailor the representations towards different tasks, addressing the needs of varying formations of urban regions and downstream tasks. Extensive experiments on five real-world datasets demonstrate that FlexiReg outperforms state-of-the-art models by up to 202% in term of the accuracy of four diverse downstream tasks using the produced urban region representations.

Electric vehicles (EVs) have the potential to serve as energy storage solutions through bidirectional charging technology, which allows them to both draw power from and feed power back into the grid, homes, or other vehicles. This capability enables EVs to reduce emissions, optimize costs, and support the grid by storing energy during periods of high production and supplying it when demand is high. In this vision paper, we focus on unlocking the potential of EVs as energy storage solutions while ensuring they remain readily available for transportation, their primary purpose. A significant research gap exists in that most current studies prioritize energy management, often using simplistic approaches that inadequately address the travel needs of EV owners. We believe the database community can be instrumental in maximizing the dual role of EVs as transportation and energy storage. We present a non-exhaustive list of research directions for various EV stakeholders, including individual EV owners, groups of independent yet cooperative EVs, commercial EV fleets, and autonomous EVs, and hope to inspire the database community for further exploration.

Due to limited driving ranges, inadequate charging facilities, and time-consuming recharging, finding an optimal charging route for electric vehicles (EVs) differs from that of other vehicle types. The time and location of charging not only impact an individual EV's travel time but also the travel time of other EVs, due to potential queuing at charging station(s). We present a novel Electric Vehicle Route Planning problem for finding the fastest route with recharging. We model this as a graph problem and propose a novel two-phase algorithm to traverse the graph to find the best charging route for each EV. We also introduce the notion of 'influence factor' to propose heuristics to find the route with the minimum travel time for an EV that avoids recharging at the charging stations that can be better utilized by other EVs. Our approach reduces 50% of total travel time over the state-of-the-art.

An increasing number of related urban data sources have brought forth novel opportunities for learning urban region representations, i.e., embeddings. The embeddings describe latent features of urban regions and enable discovering similar regions for urban planning applications. Existing methods learn an embedding for a region using every different type of region feature data, and subsequently fuse all learned embeddings of a region to generate a unified region embedding. However, these studies often overlook the significance of the fusion process. The typical fusion methods rely on simple aggregation, such as summation and concatenation, thereby disregarding correlations within the fused region embeddings. To address this limitation, we propose a novel model named HAFusion. Our model is powered by a dual-feature attentive fusion module named DAFusion, which fuses embeddings from different region features to learn higher-order correlations be-tween the regions as well as between the different types of region features. DAFusion is generic - it can be integrated into existing models to enhance their fusion process. Further, motivated by the effective fusion capability of an attentive module, we propose a hybrid attentive feature learning module named HALearning to enhance the embedding learning from each individual type of region features. Extensive experiments on three real-world datasets demonstrate that our model HAFusion outperforms state-of-the-art models across three different prediction tasks. Using our learned region embeddings leads to consistent and up to 31 % improvements in the prediction accuracy.

Trajectories that capture object movement have numerous applications, in which similarity computation between trajectories often plays a key role. Traditionally, trajectory similarity is quantified by means of non-learned measures, e.g., Hausdorff, that operate directly on the trajectories. Recent studies exploit deep learning to map trajectories tod-dimensional vectors, called embeddings. Then, some distance measure, e.g., Manhattan, is applied to the embeddings to quantify trajectory similarity. The resulting similarities are inaccurate: they only approximate the similarities obtained using the non-learned measures. As embedding distance computation is efficient, focus has been on obtaining embeddings of high accuracy. Adopting an efficiency perspective, we analyze the time complexities of both the non-learned and the learning-based approaches, finding that the time complexities of the former approaches are not necessarily higher. Through extensive experiments on open datasets, we find that only a few learning-based approaches can deliver the promised higher efficiency, when the embeddings can be pre-computed, while non-learned approaches are more efficient for one-off computations. Among the learning-based approaches, the self-attention-based ones are the fastest and the most accurate. These results have implications for the use of trajectory similarity approaches given different application requirements.

Large language models (LLMs) are advancing rapidly. Such models have demonstrated strong capabilities in learning from large-scale (unstructured) text data and answering user queries. Users do not need to be experts in structured query languages to interact with systems built upon such models. This provides great opportunities to reduce the barrier of information retrieval for the general public. By introducing LLMs into spatial data management, we envisage an LLM-based spatial database system to learn from both structured and unstructured spatial data. Such a system will offer seamless access to spatial knowledge for the users, thus benefiting individuals, business, and government policy makers alike.

Trajectory similarity measures act as query predicates in trajectory databases, making them the key player in determining the query results. They also have a heavy impact on the query efficiency. An ideal measure should have the capability to accurately evaluate the similarity between any two trajectories in a very short amount of time. Towards this aim, we propose a contrastive learning-based trajectory modeling method named TrajCL. We present four trajectory augmentation methods and a novel dual-feature self-attention-based trajectory backbone encoder. The resultant model can jointly learn both the spatial and the structural patterns of trajectories. Our model does not involve any recurrent structures and thus has a high efficiency. Besides, our pre-trained backbone encoder can be fine-tuned towards other computationally expensive measures with minimal supervision data. Experimental results show that TrajCL is consistently and significantly more accurate than the state-of-the-art trajectory similarity measures. After fine-tuning, i.e., to serve as an estimator for heuristic measures, TrajCL can even outperform the state-of-the-art supervised method by up to 56% in the accuracy for processing trajectory similarity queries.

Abstract With the increasing connectedness of vehicles, real-time spatio-temporal data can be collected from citywide road networks. Innovative data management solutions can process the collected data for the purpose of reducing travel time. However, a majority of the existing solutions have missed the opportunity to better manage the collected data for improving road safety at the network level. We propose an efficient data management framework that uses network-level data to improve road safety for citywide applications. Our framework uses a graph-based data structure to maintain real-time network-level traffic data. Based on the graph, the framework uses a novel technique to generate driving instructions for individual vehicles. By following the instructions, inter-vehicular spacing can be increased, leading to an improvement of road safety. Experimental results show that our framework improves road safety, measured based on the time to collision between vehicles, from the state-of-the-art traffic data management solutions by a large margin while achieving lower travel times compared with the solutions. The framework is also readily deployable for large-scale real-time applications due to its low computation costs.

Dynamic road network optimization has been used for improving traffic flow in an infrequent and localized manner. The development of intelligent systems and technology provides an opportunity to improve the frequency and scale of dynamic road network optimization. However, such improvements are hindered by the high computational complexity of the existing algorithms that generate the optimization plans. We present a novel solution that integrates machine learning and road network optimization. Our solution consists of two complementary parts. The first part is an efficient algorithm that uses reinforcement learning to find the best road network configurations at real-time. The second part is a dynamic routing mechanism, which helps connected vehicles adapt to the change of the road network. Our extensive experimental results demonstrate that the proposed solution can substantially reduce the average travel time in a variety of scenarios, whilst being computationally efficient and hence applicable to real-life situations.

Traffic prediction is an important and yet highly challenging problem due to the complexity and constantly changing nature of traffic systems. To address the challenges, we propose a graph and attentive multi-path convolutional network (GAMCN) model to predict traffic conditions such as traffic speed across a given road network into the future. Our model focuses on the spatial and temporal factors that impact traffic conditions. To model the spatial factors, we propose a variant of the graph convolutional network (GCN) named LPGCN to embed road network graph vertices into a latent space, where vertices with correlated traffic conditions are close to each other. To model the temporal factors, we use a multi-path convolutional neural network (CNN) to learn the joint impact of different combinations of past traffic conditions on the future traffic conditions. Such a joint impact is further modulated by an attention generated from an embedding of the prediction time, which encodes the periodic patterns of traffic conditions. We evaluate our model on real-world road networks and traffic data. The experimental results show that our model outperforms state-of-art traffic prediction models by up to 18.9% in terms of prediction errors and 23.4% in terms of prediction efficiency.

While the electric vehicle (EV) industry is facing some challenges concerning its refueling, its rapid growth in popularity is increasing these difficulties. In this paper, we demonstrate the gravity of the problems that EVs may experience for charging,both now and in the near future, and show how establishing new charging stations can be challenging. We also present the challenges in optimizing the use of charging stations by EV users. Then, we envisage opportunities for the rise of alternative charging options, such as distributed generation, crowdsourced, wireless and mobile charging stations. Additionally, we explain directions on how route and charging stations' location planning can cater to optimizing the charging infrastructure.

Intelligent traffic management solutions that leverage machine learning have gained a lot of interest in recent years. These techniques, however, cannot be deployed in real-world settings at a desirable pace due to technological barriers. Thus, easily customizable, realistic simulation environments are needed to train and verify the effectiveness of machine learning algorithms for traffic control. We propose an easily extendable traffic simulation system named e-SMARTS to allow researchers to experiment with novel data-driven traffic management algorithms in a setup that mimics real-world traffic conditions. We demonstrate the flexibility of e-SMARTS using widely researched traffic management solutions for Autonomous Intersection Management (AIM). In the demonstration, we present several pluggable algorithms for AIM and show that these computationally efficient algorithms can achieve effective and safe results.

Graph combinatorial optimization (CO) is a widely studied problem with use-cases stemming from many fields. Typically, in real-world applications, the features of a graph tend to change over time (e.g. traffic congestion, or travel time), thus, finding a solution to the dynamic graph CO problem is critical. In recent years, using deep learning techniques to find heuristic solutions for NP-hard CO problems has gained much interest as these learned heuristics can find near-optimal solutions efficiently. However, most of the existing methods for learning heuristics focus on static CO problems. The dynamic nature makes NP-hard CO problems much more challenging to learn, and the existing methods fail to find reasonable solutions. We propose a novel architecture named Graph Temporal Attention with Reinforcement Learning (GTA-RL) to learn heuristic solutions for dynamic versions of graph CO problems. We then extend our architecture to learn heuristics for the real-time version of CO problems where all input features of a problem are not known a priori, but rather learned in real-time. A detailed experimental evaluation against several state-of-the-art learning-based algorithms and optimal solvers demonstrates the efficiency and effectiveness of our approach.

With increasing connectivity and autonomy in traffic eco-systems, Autonomous Intersection Management (AIM) has attracted strong attention from the research community. AIM helps optimize traffic by coordinating the trajectory of connected vehicles around intersections. Most of the existing AIM solutions are developed for single-objective optimization problems that are focused on improving traffic flow. A complete AIM solution needs to perform bi-objective optimization that considers both traffic flow and safety. However, the computational complexity for achieving both objectives is significantly high with the existing solutions, especially when traffic demand is stochastic. We address the limitations of the existing solutions using deep reinforcement learning (deep RL) that helps solve complex problems efficiently. Our solution uses two types of RL agents. The first type is intersection-level agents, which generate theoretically sound trajectory plans for individual vehicles approaching intersections. The second type is vehicle-level agents that control vehicles' actual trajectories around the intersections based on the plans. Both agents incorporate traffic flow and safety constraints into their decision making. Our experimental results show that our solution achieves a high safety level with a minimum impact on travel time.

Due to the importance of road freight, there is a significant cost of delaying freight vehicles on the road. In this work, we focus on freight vehicle optimization by reducing delays at intersections. Our simulation study evaluates the effectiveness of an autonomous intersection management strategy that prioritizes connected freight vehicles using intelligent traffic lights. We simulate a wide range of traffic scenarios on our microscopic traffic simulator. Our results show that the strategy can help reduce the delay of freight vehicles with a minimal impact on other vehicles in a real road network. Our simulations also reveal the scenarios where the strategy works best and where it should be avoided. Effects of individual parameters are also measured through simulations.

COVID-19 has brought about substantial social, economic and health related burdens, motivating different control measures from policy makers worldwide. Contact tracing plays a pivotal role in the COVID-19 era. However, contact tracing is by nature entirely retrospective: it can only identify contacts of known or suspected cases. Our proposed system is prospective, aiming to 'create' networks that will ultimately make contact tracing and pandemic management easier. As contact tracing seeks to reconstruct the underlying interaction network, we can improve the process by reducing the complexity of contact network structure; we introduce a method for reducing contact network complexity through strategic scheduling. The method functions through pairwise comparison of individual trajectories in a coordinate space of activities, locations, and time intervals. We demonstrate the method through a simulated scenario where individuals (students) register for activities using a mobile application in a campus. The application then applies our algorithm to provide individuals with schedules that reduce the complexity of the overall network, without compromising individual privacy.

Traffic forecasting plays a vital role in traffic management systems. Recently, deep learning models have been applied to citywide traffic forecasting. However, the existing work models and predicts traffic at a single (dense) resolution, making it challenging to capture long-range spatial dependencies or high-level traffic dynamics. This shortcoming limits the accuracy of prediction and results in computationally expensive models. We propose a traffic forecasting model based on deep convolutional networks to improve the accuracy of citywide traffic forecasting. Our model uses a hierarchical architecture that captures traffic dynamics at multiple spatial resolutions. Based on this architecture, we apply a multi-task learning scheme, which trains the model to predict traffic at different resolutions. Our model helps provide a coherent understanding of traffic dynamics by capturing spatial dependencies between different regions of a city. Experimental results on multiple real datasets show that our model can achieve competitive results compared to complex state-of-the-art approaches while being more computationally efficient.

User trajectory data is becoming increasingly accessible due to the prevalence of GPS-equipped devices such as smartphones. Many existing studies focus on querying trajectories that are similar to each other in their entirety. We observe that trajectories partially similar to each other contain useful information about users’ travel patterns which should not be ignored. Such partially similar trajectories are critical in applications such as epidemic contact tracing. We thus propose to query trajectories that are within a given distance range from each other for a given period of time. We formulate this problem as a sub-trajectory similarity join query named as the STS-Join. We further propose a distributed index structure and a query algorithm for STS-Join, where users retain their raw location data and only send obfuscated trajectories to a server for query processing. This helps preserve user location privacy which is vital when dealing with such data. Theoretical analysis and experiments on real data confirm the effectiveness and the efficiency of our proposed index structure and query algorithm.

Online navigation systems assume a person can follow a given route from origin to destination. Nonetheless, spatial cognition studies show that wayfinding is a complex, highly adaptive process and that route planning is incremental rather than prescriptive. Indeed, people may deviate from their originally chosen route for a number of reasons including navigation errors, especially when the environment is unfamiliar. Even in familiar places, certainty in wayfinding is highly unlikely to be completely achieved. Consequently, when people make a wrong turn or miss an exit, even the best reroute to the destination may add several minutes to the originally planned travel time. This work formally defines the novel problem of finding a path such that, when navigation errors occur, recovering is not as costly. We call this approach the most recoverable path. This subtle change in the route planning problem – i.e., considering error recovery costs – invalidates using dynamic programming, such as in shortest path algorithm solutions. We therefore introduce a novel, readily applicable, fast heuristic to this NP-hard problem. The benefits of the most recoverable path are manifold: long detours are avoided, actual travel time is reduced, and it is comparable to its shortest counterpart in terms of length.

We study the problem of tracking the movement of groups using sparse trajectory data extracted from Location Based Social Networks (LBSNs). Tracking group movement using LBSN data is challenging because the data may contain a large amount of noise due to the lack of stability in group entity, spatial extent and posting time. We propose a first-of-its-kind solution, Group Kalman Filter (GKF), which aims to improve the effectiveness of group tracking by predicting the spatial properties of groups with a group movement model. Our experiments with real LBSN data and synthetic LBSN data show that GKF can detect groups and predict group movement with a high level of accuracy and efficiency.

Each year, millions of people either die or get injured due to road incidents. Thus, integrating safety optimization techniques into future traffic systems is of utmost importance. Emerging connected vehicle technologies have enabled ways to manage traffic networks with optimization goals such as travel time efficiency, fuel efficiency. However, these existing studies have focused less on maximizing traffic safety. Increasing space between vehicles in the road network with an acceptable travel time increase will help to improve the safety of the system. We propose the Platooning Graph, which is capable of modelling the inter-vehicular spacing optimization problem and we provide a fast and readily deployable algorithm to find a good approximate solution. Using microscopic traffic simulations, we demonstrate how the proposed method can improve safety, with minimal impact on travel time.

In the coming era of connected autonomous vehicles, data-driven traffic optimization will reach its full potential. By collecting highly detailed real-time traffic data from sensors and vehicles, a traffic management system will have the full view of the entire road network, allowing it to plan traffic in a virtual world that replicates the real road network. This will bring significant innovations to transport-domain applications. We prototype a traffic management system that can perform traffic optimization with connected autonomous vehicles. We propose two route assignment algorithms that aim to reduce traffic delays by reducing intersecting routes. The proposed algorithms and two state-of-the-art route assignment algorithms are implemented in the prototype system. We evaluate the algorithms with both synthetic and real road networks. The experimental results show that the proposed algorithms outperform competitors in terms of the travel times of the routes.

Activity-Based ride-sharing is a new paradigm which enhances the current model based on fixed origins and destinations, namely trip-based ride-sharing. In this new model, a user issues a ride-sharing request with his origin and the activity he wants to perform at any convenient destination. Then, the system computes the travel plans and users will be suggested the optimal destinations, which may be common to many users. In this way, the set of possible destinations for each user is expanded and further distance savings can be made as we have already shown in our previous work [1, 3]. In this paper, we show Activity-Based ride-sharing in action through our web-service-based framework, which is able to suggest routes and meeting points for many users in a city-scale scenario.

There are many real world applications that require to identify movement of users such as identifying movement corridors, most popular paths, and nearest neighbours. If one is not given trajectories mapping to movement of people but rather sporadic location data, such as location based social network data, finding movement related information becomes difficult. Rather than processing all points in a data set given a query, a clever approach is to construct a graph, based on user locations, and query this graph for all queries. One example is the shortest path graph. However the shortest path graph can be inefficient and ineffective analysing movement, as it calculates the graph considering all points in a data set. We propose the stepping stone graph, which calculates graph considering point pairs rather than all points, that focuses on local possible movement, making it both efficient and effective for location based social network related queries. We demonstrate its uses by applying it in the aforementioned domain and comparing with the shortest path graph. We also compare its properties to a range of other graphs.

Microscopic traffic simulators play a major role to carry research on transportation problems. Microscopic traffic simulation is powerful because it enables efficient analysis of complex traffic problems to the highest level of detail. We developed Scalable Microscopic Adaptive Road Traffic Simulator (SMARTS) [14] that can perform large-scale simulations at a high speed by utilizing distributed computing resources. Previous results show that SMARTS can run 1.14 times faster than real time when simulating one million vehicles for the city of Melbourne on 30 distributed processors, while producing highly accurate simulation results. SMARTS' pluggable architecture allows it to be easily extended to simulate specific scenarios of interest to users. In this demonstration we show how SMARTS can be used to simulate an intersection design, the P-turn, in a major intersection of Melbourne. Our simulation shows the impact of the design on the traffic flow, confirming the justification for introduction of the particular intersection. The demo can be used as a template for future use of the simulator for other traffic problems.

We study the problem of continuous maintenance of range sum heat maps over dynamically updating data objects. The range sum (RS) here refers to the sum of the weights of the data objects enclosed by a given range (rectangle) R. Range sum problems are useful in spatio-temporal data analytics and decision making processes. Recent studies on range sum problems focus on computing the MaxRS query, which finds a location to place a rectangle R such that its RS is maximized. In real applications, knowing only the location with the maximum RS may be insufficient, because decision making is a multi-factor process where maximizing the RS may just be one of the factors. It is also important to gain an overview of the RS distribution at different locations, so that decisions can be made based on global knowledge. We therefore propose to compute a range-sum heat map that visualizes the RS value for every location in a data space. Considering that data objects may be inserted into or removed from the data space dynamically, we further study the continuous maintenance of range-sum heat maps over dynamically updating data objects. We adapt algorithms to compute range-sum heat maps and to perform heat map updates. We build a demo system to showcase the usefulness of range sum heat maps and the effectiveness of the adapted algorithms.

Traffic congestion is a serious problem that is only expected to get worse in the future. Statistics shows that half of traffic congestion is caused by temporary disruptions like accidents. These events have dramatic impact on road network availability and cause huge delays for commuters. Also, they are usually unexpected and hard to manage by traffic authorities. State-of-the-art navigation systems started to provide real-time information about traffic conditions to help users make better routing decisions. However, traffic in the road network changes rapidly and the advice calculated now may not be valid after few minutes. This is especially critical in the presence of traffic incidents, where the impact of the incident could cause traffic to propagate to nearby roads. Thus, it is important for navigation systems to consider the evolution and future impact of traffic events. In this work, we present a navigation system that uses faster than realtime simulations to predict the evolution of traffic events and help drivers proactively avoid congestion caused by events. The system can subscribe to real-time traffic information and forecast the traffic conditions using fast simulations. We evaluate our approach through extensive experiments to test the performance and accuracy of the simulator with real data obtained from TomTom Traffic API. Also, we test the quality of navigation advice in realistic settings and show that our solution is able to help drivers avoid congested areas in cases where even real-time update methods lead drivers to congested routes.

Ride-sharing is rapidly becoming an alternative form of transportation mainly due to its economic benefits. Existing research on ridesharing aims to optimally match trajectories between people with pre-selected destinations. In this paper, we show better ride-sharing arrangements are possible when users are presented with more destinations and agree on a common destination. Given a set of points of interest (POIs) and a set of users, our approach presents destination POIs and computes ride-sharing plans. Each arrangement for a subset of users that fit in a car can be presented as a minimum Steiner tree (MST) problem. An optimal solution of the overall problem minimizes the total length of all the MSTs. The problem is a version of the set cover problem and is NP-hard. We first develop a series of baseline methods which use a popular MST algorithm. Then, we propose our method which uses constraints on intermediary points where users can meet to share rides. These constraints reduce the time complexity significantly and our method is up to two orders of magnitude faster than the best baseline method. Since our algorithm finds the subsets of users and POIs for each arrangement, we define and solve a new type of MST problem as a first step. Our experiments show that our method can provide a fast and readily deployable solution for real world large city scenarios.

A large number of self-driving cars will be on roads in the near future. They will change traffic significantly. Self-driving cars can infer and decide travel paths from passenger input. Passengers do not need to involve in route planning. This provides great opportunities for traffic management systems to collaborate and achieve more efficient traffic management. By knowing most source-destination pairs of the passengers, we envisage an increasingly integrated system that can optimize routes and traffic lights to minimize travel time. By optimally scheduling time of travel and traffic light switching timings, such systems can also provide simultaneously emergency corridors for high priority vehicles such as police cars, fire engines, and ambulances when required.

Since its introduction a decade ago, differential privacy has been deployed and adapted in different application scenarios due to its rigorous protection of individuals' privacy regardless of the adversary's background knowledge. An urgent open research issue is how to query/release time evolving datasets in a differentially private manner. Most of the proposed solutions in this area focus on releasing private counters or histograms, which involve low sensitivity, and the main focus of these solutions is minimizing the amount of noise and the utility loss throughout the process. In this paper we consider the case of releasing private numerical values with unbounded sensitivity in a dataset that grows over time. While providing utility bounds for such case is of particular interest, we show that straightforward application of current mechanisms cannot guarantee (differential) privacy for individuals under an open-world assumption where data is continuously being updated, especially if the dataset is updated by an outlier.

Microscopic traffic simulators are important tools for studying transportation systems as they describe the evolution of traffic to the highest level of detail. A major challenge to microscopic simulators is the slow simulation speed due to the complexity of traffic models. We have developed the Scalable Microscopic Adaptive Road Traffic Simulator (SMARTS), a distributed microscopic traffic simulator that can utilize multiple independent processes in parallel. SMARTS can perform fast large-scale simulations. For example, when simulating 1 million vehicles in an area the size of Melbourne, the system runs 1.14 times faster than real time with 30 computing nodes and 0.2s simulation timestep. SMARTS supports various driver models and traffic rules, such as the car-following model and lane-changing model, which can be driver dependent. It can simulate multiple vehicle types, including bus and tram. The simulator is equipped with a wide range of features that help to customize, calibrate, and monitor simulations. Simulations are accurate and confirm with real traffic behaviours. For example, it achieves 79.1% accuracy in predicting traffic on a 10km freeway 90 minutes into the future. The simulator can be used for predictive traffic advisories as well as traffic management decisions as simulations complete well ahead of real time. SMARTS can be easily deployed to different operating systems as it is developed with the standard Java libraries.

A Group Nearest Neighbor (GNN) query finds a point of interest (POI) that minimizes the aggregate distance for a group of users. In current systems, users have to reveal their exact, often sensitive locations to issue a GNN query. This calls for private GNN queries. However, existing methods for private GNN queries either are computationally too expensive for mobile phones or cannot resist sophisticated attacks. Our approach can efficiently and effectively process an important variant of private GNN queries: queries that minimize the maximum distance for any user in the group. To achieve high efficiency we develop a distributed multi-party private protocol to compute the maximum function. Our method exploits geometric constraints to prune POIs and avoids unnecessary data disclosure. In contrast to current state of the art multi-party private protocols, our proposed protocol does not rely on cryptography and has a fast runtime. Importantly, a user does not have to provide a location directly, even in imprecise form.

Recent advancements in data mining coupled with the ubiquity of mobile devices has led to the possibility of mining for events in real-time. We introduce the problem of mining for an individual's encounters. As people travel, they may have encounters with one another. We are interested in detecting the encounters of traveling individuals at the exact moment in which each of them occur. A simple solution is to use a nearest neighbor search to return potential encounters, this results in slow query response times. To mine for encounters in real-time, we introduce a new algorithm that is efficient in capturing encounters by exploiting the observation that just the neighbors in a defined proximity needs to be maintained. Our evaluation demonstrates that our proposed method mines for encounters for millions of individuals in a city area within milliseconds.

A group of friends located at their working places may want to plan a trip to visit a shopping center, have dinner at a restaurant, watch a movie at a theater, and then finally return to their homes with the minimum total trip distance. For a group of spatially dispersed users a group trip planning (GTP) query returns points of interests (POIs) of different types such as a shopping center, a restaurant and a movie theater that minimize the aggregate trip distance for the group. The aggregate trip distance could be the sum or maximum of the trip distances of all users in the group, where the users travel from their source locations via the jointly visited POIs to their individual destinations. In this paper, we develop both optimal and approximation algorithms for GTP queries for both Euclidean space and road networks. Processing GTP queries in real time is a computational challenge as trips involve POIs of multiple types and computation of aggregate trip distances. We develop novel techniques to refine the POI search space for a GTP query based on geometric properties of ellipses, which in turn significantly reduces the number of aggregate trip distance computations. An extensive set of experiments on a real and synthetic datasets shows that our approach outperforms the most competitive approach on an average by three orders of magnitude in terms of processing time.

Major navigation companies have resorted to crowdsourcing for obtaining traffic data to improve their services. In fact, a new generation of navigation systems are emerging for the sole purpose of connecting drivers on the road (Waze.com) so that they benefit from each other. The focus of these efforts is on real-time traffic estimation. While obtaining real-time data is desirable and has great benefits, it is still limited, given the potential of the detailed individual data from drivers. For example, commuters in a city have valuable knowledge about their city as a result of their daily commute over many years. Using drivers as mere traffic sensors and aggregating their data desposes off any human knowledge that exists in their choices. In this work, we demonstrate a social navigation system that can help drivers avoid road incidents using expert advice in real-time without explicitly consulting drivers but through an automated system built on top of a location-based social network. In our system, we do not aggregate data from individual users and we instead outsource the task of finding a route that best avoids incidents by looking up drivers' old choices.

We introduce a new type of spatial query, Optimal Accessible Location (OAL) query. When a set of paths is provided the query finds the best location from a set of locations that has the optimal accessibility from these paths. OAL queries have many applications such as the selection of the optimal location for a mobile facility such as a food truck or selection of a venue for an event. We exploit geometric properties and develop pruning techniques to eliminate unrelated path segments as well as locations. Our experimental results demonstrate that we provide a readily deployable solution for real-life applications.

Localization schemes used for positioning are currently based on either range-based or range-free principles. We propose a unified approach that combines the strengths of both methods while overcoming their limitations. Range-based methods rely on taking reliable measurements in which geometric techniques are then applied. These techniques are very susceptible to imprecision in captured measurements. Range-free methods do not consider the actual numerical sensor value, rather comparing magnitudes across sensors. These comparisons are not always reliable and may lead to an accumulation of errors. Our unified approach mitigates these effects by first using a range-based method to determine an approximate location followed by a range-free method to refine the positioning estimate further. Our experiments show the mean estimation error improves when applying our localization scheme to a Bluetooth system.

Trajectory data does not only show the location of users over a period of time, but also reveals a high level of detail regarding their lifestyle, preferences and habits. Hence, it is highly susceptible to privacy concerns. Trajectory privacy has become a key research topic when sharing/exchanging trajectory datasets. Most existing studies focus on protecting trajectory data through obfuscating, anonymising or perturbing the data with the aim to maximize user privacy. Although such approaches appear plausible, our work suggests that precise trajectory information can be inferred even from other sources of data. We consider the case in which a location service provider only shares POI query results of users with third parties instead of exchanging users' raw trajectory data to preserve privacy. We develop an inference algorithm and show that it can effectively approximate original trajectories using solely the POI query results.

Research on cognitive science indicates that humans often use different criteria for route selection. An alternative type of spatial proximity search on road networks recently has been proposed to find the easiest-to-reach neighboring object with the smallest navigation complexity. This paper presents an evaluation to compare the effectiveness of easiest-to-reach neighbor query against a classic nearest neighbor query in a real-world setting. Our user study demonstrates usability of the new spatial query type and suggests people may not always care about travel distance most. To provide flexibility to accommodate different requirements, we also show how to achieve tradeoff between navigation complexity and travel distance for advanced navigational assistance.

Privacy concerns place a great impediment to publishing and/or exchanging trajectory data across companies and institutions. This has urged researchers to address privacy issues prior to trajectory data release. Currently, privacy preserving solutions distort original data unnecessarily, hence, degrade data utility and make such data less useful for third parties. We consider a trajectory as a sequence of stops and moves, and propose an approach that exploits features of a trajectory as means for preserving privacy while maintaining a high level of utility. We introduce the concept of sensitivity for stops based on the assumption that they are more vulnerable to privacy threats. We propose an efficient algorithm that either substitutes sensitive stop points of a trajectory with moves from the same trajectory or introduces a minimal detour if a less sensitive stop can not be found on the same route. Our experiments shows that our method balances user privacy and data utility: it protects privacy through preventing an adversary from making inferences about sensitive stops while maintaining a high level of data similarity to the original dataset.

We study the problem of finding the shortest route between two locations that includes a stopover of a given type. An example scenario of this problem is given as follows: “On the way to Bob's place, Alice searches for a nearby take-away Italian restaurant to buy a pizza.” Assuming that Alice is interested in minimizing the total trip distance, this scenario can be modeled as a query where the current Alice's location (start) and Bob's place (destination) function as query points. Based on these two query points, we find the minimum detour object (MDO), i.e., a stopover that minimizes the sum of the distances: 1) from the start to the stopover, and 2) from the stopover to the destination. In a realistic location-based application environment, a user can be indecisive about committing to a particular detour option. The user may wish to browse multiple (k) MDOs before making a decision. Furthermore, when a user moves, the k{\rm MDO} results at one location may become obsolete. We propose a method for continuous detour query (CDQ) processing based on incremental construction of a shortest path tree. We conducted experimental studies to compare the performance of our proposed method against two methods derived from existing k-nearest neighbor querying techniques using real road-network data sets. Experimental results show that our proposed method significantly outperforms the two competitive techniques.

Continuous queries in road networks have gained significant research interests due to advances in GIS and mobile computing. Consider the following scenario: "A driver uses a networked GPS navigator to monitor five nearest gas stations in a road network." The main challenge of processing such a moving query is how to efficiently monitor network distances of the k nearest and possible resultant objects. To enable result monitoring in real-time, researchers have devised techniques which utilize precomputed distances and results, e.g., the network Voronoi diagram (NVD). However, the main drawback of preprocessing is that it requires access to all data objects and network nodes, which means that it is not suitable for large datasets in many real life situations. The best existing method to monitor kNN results without precomputation relies on executions of snapshot queries at network nodes encountered by the query point. This method results in repetitive distance evaluation over the same or similar sets of nodes. In this paper, we propose a method called the local network Voronoi diagram (LNVD) to compute query answers for a small area around the query point. As a result, our method requires neither precomputation nor distance evaluation at every intersection. According to our extensive analysis and experimental results, our method significantly outperforms the best existing method in terms of data access and computation costs.

Studies in cognitive science have shown that people have differ-ent optimization goals in mind for route selection: beyond shortest travel distance (or time), criteria such as smallest number of turns or straightest path are often considered. A common query that a traveller in a foreign city may ask is “where is a facility of type X”. When multiple facilities of the same type are available in the nearby area, usually not the nearest neighbor but the one which is easiest to find is preferred for giving instructions by locals, especially in an unfamiliar and complex urban environment. This paper studies a novel type of neighboring object selection problem, taking cog-nitive complexity of navigation into account. The main difficulty arises from incorporating spatial chunking and landmark informa-tion into neighbor comparisons. We propose an algorithm based on network expansion, which uses incremental processing of graph transformation that models instruction complexity. Our approach can efficiently find the easiest-to-reach neighbor with the guaran-teed smallest navigation cost. Through experimental evaluation on real road networks, the performance of the proposed algorithm is demonstrated under various settings. Our comparison results reveal that on average the travel distance of the easiest-to-reach neighbor is only 19.3 % longer than that of the nearest neighbor, whereas the navigation cost can achieve a 64.8 % reduction.

In many applications involving spatial objects, we are only interested in objects that are directly visible from query points. In this paper, we formulate the visible k nearest neighbor (VkNN) query and present incremental algorithms as a solution, with two variants differing in how to prune objects during the search process. One variant applies visibility pruning to only objects, whereas the other variant applies visibility pruning to index nodes as well. Our experimental results show that the latter outperforms the former. We further propose the aggregate VkNN query that finds the visible k nearest objects to a set of query points based on an aggregate distance function. We also propose two approaches to processing the aggregate VkNN query. One accesses the database via multiple VkNN queries, whereas the other issues an aggregate k nearest neighbor query to retrieve objects from the database and then re-rank the results based on the aggregate visible distance metric. With extensive experiments, we show that the latter approach consistently outperforms the former one.

ACM International Conference on Advances in Geographic Information Systems (SIGSPATIAL)

This demonstration program presents the V*-kNN algorithm, an efficient algorithm to process moving k nearest neighbor queries (MkNN). The V*-kNN algorithm is based on a safe-region concept called the V*-Diagram. By incrementally maintaining the V*-Diagram, V*-kNN continuously provides accurate MkNN query results and supports dynamically changing values of k. Our approach exploits information regarding the current location of the query point and the search space in addition to the data objects. As a result, the V*-kNN has much smaller IO and computation costs than existing methods.

Existing techniques for autonomous indoor navigation are often environment-specific and thus limited in terms of their applicability. In this paper, we take a fundamentally different approach to indoor navigation and propose an active environment based navigation system. We argue that for a versatile navigation system the environment itself should provide spatial information. In our proposed approach, navigation is based on the concept of space partitions where the location of an agent is approximated by the closest partition. We show that Radio Frequency Identification (RFID) technology is a viable option for generating space partitions. We present a cost effective deployment strategy for passive RFID tags to construct a complete partitioning of the environment. A sparse deployment of tags leads to coarse partitioning, which in turn allows an agent to only approximate its position. We introduce a path planning algorithm that enables an agent reach its destination with a small overhead compared to the shortest path algorithm assuming precise information. Our experiments show that the deployment allows efficient path planning even under a large degree of imprecision.

With recent advances in mobile computing technologies, mobile devices can now render 3D objects realistically. Many users of these devices such as tourists, mixed-reality gamers, and rescue officers, need real-time retrieval of 3D objects over a wireless network. Due to bandwidth and latency restrictions in mobile settings, efficient continuous retrieval of 3D objects remains a challenge. In this paper, we describe a motion-aware approach to this problem. We first introduce multi-resolution storage and retrieval methods for 3D data, which restrict access to only the necessary content based on the client's motion pattern. We then propose a motion-aware buffer management technique as well as an efficient index using multi-resolution representations of objects. Our experiments demonstrate the effectiveness of our solution to continuous retrieval of complex spatial data in mobile settings.

Monitoring moving objects is one of the key application domains for sensor networks. In the absence of cooperative objects and devices attached to these objects, target tracking algorithms have to be used for monitoring. In this paper, we present that many of the applications of moving object monitoring systems could be addressed with low-frequency snapshot-based queries. With the realization of this query type, we show that existing target tracking algorithms may not be the least expensive solutions. We introduce an approach that uses two alternating strategies. We maintain a cheap low-quality knowledge of moving objects' location between snapshots and trigger expensive sensor readings only when a snapshot period has elapsed. With extensive experiments we show that our approach is significantly more energy efficient than established methods. It is also more effective than existing data-and-query centric in-network query processing schemes as it can maintain object identities between snapshots.

The moving k nearest neighbor (M k NN) query finds the k nearest neighbors of a moving query point continuously. The high potential of reducing the query processing cost as well as the large spectrum of associated applications have attracted considerable attention to this query type from the database community. This paper presents an incremental safe-region-based technique for answering M k NN queries, called the V*-Diagram. In general, a safe region is a set of points where the query point can move without changing the query answer. Traditional safe-region approaches compute a safe region based on the data objects but independent of the query location. Our approach exploits the current knowledge of the query point and the search space in addition to the data objects. As a result, the V*-Diagram has much smaller IO and computation costs than existing methods. The experimental results show that the V*-Diagram outperforms the best existing technique by two orders of magnitude.

For monitoring moving objects via wireless sensor networks, we introduce two aggregate query types: distinct entries to an area and the number of objects in that area. We present a new technique, Distributed Euler Histograms (DEHs), to store and query aggregated moving object data. Aggregate queries occur in a variety of applications ranging from wildlife monitoring to traffic management. We show that DEHs are significantly more efficient, in terms of communication and data storage costs, than techniques based on moving object identifiers and more accurate than techniques based on simple histograms.

We describe a distributed quadtree index for enabling more powerful access on complex data over P2P networks. It is based on the Chord method. Methods such as Chord have been gaining usage in P2P settings to facilitate exact-match queries. The Chord method maps both the data keys and peer addresses. Our work can be applied to higher dimensions, to various data types, i.e., other than spatial data, and to different types of quadtrees. Finally, we can use other key-based methods than the Chord method as our base P2P routing protocol and index scale well. The index also benefits from the underlying fault-tolerant hashing-based methods by achieving a nice load distribution among many peers. We can seamlessly execute a single query on multiple branches of the index hosted by a dynamic set of peers.