ACM Transactions on

Spatial Algorithms and Systems (TSAS)

Latest Articles

In-Route Task Selection in Spatial Crowdsourcing

Consider a city’s road network and a worker who is traveling on a given path from a starting point s to a destination d (e.g., from school or work to home) in said network. Consider further that there is a set of tasks in the network available to be performed, where each such task takes a certain amount of time to be completed and yields a... (more)


 ACM Transactions on Spatial Algorithms and Systems (TSAS) is a scholarly journal that publishes high-quality papers on all aspects of spatial algorithms and systems and closely related disciplines. The journal welcomes articles on any of the above topics or closely related disciplines in the context of various computing architectures including parallel and distributed networks of computers, multiprocessing computers, or new mobile devices and sensors. READ MORE

Call-for-papers: ACM TSAS has issued a call for papers for a Special issue on Urban Mobility: Algorithms and Systems. Please use manuscriptcentral ( to submit articles, check the status of articles and for reviewing tasks.

Forthcoming Articles

Editorial: Special Issue on the Best Papers from the 2018 ACM SIGSPATIAL Conference

Map-Matching Using Shortest Paths

We consider several variants of the map-matching problem, which seeks to find a path Q in graph G that has the smallest distance to a given trajectory P (which is likely not to be exactly on the graph). In a typical application setting, P models a noisy GPS trajectory from a person traveling on a road network, and the desired path $Q$ should ideally correspond to the actual path in G that the person has traveled. Existing map-matching algorithms in the literature consider all possible paths in G as potential candidates for Q. We find solutions to the map-matching problem under different settings. In particular, we restrict the set of paths to shortest paths, or concatenations of shortest paths, in G. As a distance measure, we use the Fr\'echet distance, which is a suitable distance measure for curves since it takes the continuity of the curves into~account.

Transit Signal Priority along a signalized arterial: A passenger-based Approach

This paper develops a passenger-based priority for transit buses by balancing the trade-offs between the benefits at major streets and delays on side streets. A rule-based transit signal priority (TSP) is set to assign priority to scheduled-based transit vehicles based on: their schedule adherence, passenger occupancy, and passengers waiting at downstream stops. The minimum number of bus passengers required to receive priority is obtained using deterministic queueing theory for the two cases of green extension and red truncation. VISSIM simulation software is used to evaluate the performance of the developed TSP approach, comparing it with: existing, unconditional and no-TSP scenarios. This evaluation assessed performance measures for major streets, crossing streets and the network level. The simulation demonstrated that a passenger-based TSP results in a significant decrease in travel time and side street delay, compared to existing priority measures (buses will receive priority once every three minutes) on the corridor.

Intelligent Intersection: Two-Stream Convolutional Networks for Real-time Near-Accident Detection in Traffic Video

In Intelligent Transportation System, real-time systems that monitor and analyze road users become increasingly critical as we march toward the smart city era. Vision-based frameworks for Object Detection, Multiple Object Tracking, and Traffic Near Accident Detection are important applications of Intelligent Transportation System, particularly in video surveillance and etc. Although deep neural networks have recently achieved great success in many computer vision tasks, a uniformed framework for all the three tasks is still challenging where the challenges multiply from demand for real-time performance, complex urban setting, highly dynamic traffic event, and many traffic movements. In this paper, we propose a two-stream Convolutional Network architecture that performs real-time detection, tracking, and near accident detection of road users in traffic video data. The two-stream model consists of a spatial stream network for Object Detection and a temporal stream network to leverage motion features for Multiple Object Tracking. We detect near accidents by incorporating appearance features and motion features from two-stream networks. Using aerial videos, we propose a Traffic Near Accident Dataset (TNAD) covering various types of traffic interactions that is suitable for vision-based traffic analysis tasks. Our experiments demonstrate the advantage of our framework with an overall competitive qualitative and quantitative performance at high frame rates on the TNAD dataset.

Differentiating Population Spatial Behavior using Representative Features of Geospatial Mobility (ReFGeM)

Understanding how humans use and consume space by comparing stratified groups, either through observation or controlled study, is key to designing better spaces, cities, and policies. GPS data traces provide detailed movement patterns of individuals but can be difficult to interpret due to the scale and scope of the data collected. For actionable insights, GPS traces are usually reduced to one or more features which express the spatial phenomenon of interest. However, it is not always clear which spatial features should be employed, and substantial effort can be invested into designing features which may or may not provide insight. In this paper we present an alternative approach: a standardized feature set with actionable interpretations that can be efficiently run against many datasets. We show that these features can distinguish between disparate human mobility patterns, although no single feature can distinguish them alone.

Efficient DropBox Deployment towards Improving Post Disaster Information Exchange in a Smart City

The networking research community proposes the use of smart phone based delay tolerant networks, for post-disaster situational information dissemination. Knowledge about the urban mobility pattern of the smartphone users plays a pivotal role in successful dissemination of situational information. In this paper, we first propose a human movement model for post disaster scenario in a smart city that characterizes mobility pattern of smartphone users like volunteers, rescue workers, victims, etc. Literature survey and simulations reveal that network performance improves if the proposed mobility model is applied with an appropriate DropBox deployment strategy. Consequently, we next propose a utility based DropBox deployment scheme, to be fused into the proposed movement model to enhance network performance of the underlying routing protocols. In this scheme, utility of a location is calculated on the basis of distance from the disaster point, number of merging paths, density of nodes and the volume of messages exchanged. We provide analytical validations of the proposed movement model and the DropBox deployment scheme. Extensive simulation is performed using ONE simulator to evaluate the comparative performance of the presented movement model with respect to other state-of-the-art models while using the proposed DropBox deployment scheme. We also compare the performance of the proposed deployment scheme with some existing deployment schemes while using the proposed movement model. Simulation results justify that our movement model when applied with the proposed DropBox deployment scheme, improves network performances in terms of delivery ratio, overhead ratio and average residual energy at the cost of tolerable latency.

Turbo-GTS: A Fast Framework of Optimizing Task Throughput for Large-scale Mobile Crowdsourcing

In mobile crowdsourcing, workers are financially motivated to perform as many self-selected tasks as possible to maximize their revenue. Unfortunately, the existing task scheduling approaches in mobile crowdsourcing fail to consider task execution duration and do not scale for massive tasks and large geographic areas. In this paper, we propose a novel framework, Turbo-GTS, in support of large-scale Geo-Task Scheduling (GTS), with the objective of identifying an optimal task assignment for each worker in order to maximize the total number of tasks that can be completed for an entire worker group, given the geographic locations of each task and each worker. Since the exact solution to the GTS problem is computationally intractable, we first propose two sub-optimal approaches (LCPF and NUD-IC) based on particle filtering and DBSCAN for the Single Worker Geo-Task Scheduling (SGTS) problem. We then extended our work to solve the Multi-Worker Geo-Task scheduling (MGTS) problem by proposing two space partitioning-based methods (QT-NNH and QT-NUD), which leverage the point-region quadtree to ensure workload balancing. The effectiveness and efficiency of the four proposed approximate solutions are verified by our extensive experiments using both real and synthetic data. Compared with the state-of-the-art approaches, our proposed solutions are able to return a higher number of completed tasks for the worker group while reducing the computation cost by up to three orders of magnitude when coping with massive tasks distributed in large geographic areas.

Distributed Subtrajectory Join on Massive Datasets

Joining trajectory datasets is a significant operation in mobility data analytics and the cornerstone of various methods that aim to extract knowledge out of them. In the era of Big Data, the production of mobility data has become massive and, consequently, performing such an operation in a centralized way is not feasible. In this paper, we address the problem of Distributed Subtrajectory Join processing by utilizing the MapReduce programming model. Compared to traditional trajectory join queries, this problem is even more challenging since the goal is to retrieve all the ?maximal? portions of trajectories that are ?similar?. We propose three solutions: (i) a well-designed basic solution, coined DTJb, (ii) a solution that uses a preprocessing step that repartitions the data, labeled DTJr, and (iii) a solution that, additionally, employs an indexing scheme, named DTJi. In our experimental study, we utilize a 56GB dataset of real trajectories from the maritime domain, which,to the best of our knowledge, is the largest real dataset used for experimentation in the literature of trajectory data management. The results show that DTJi performs up to 16× faster compared with DTJb, 10× faster than DTJr and 3× faster than the closest related state of the art algorithm.

Social Force Modeling and Calibration of Pedestrian Crowd Motion Considering Slow-Moving Vehicle Influence in Open Area

Understanding the intention of pedestrians is crucial to various transportation related applications, especially to the interaction between pedestrians and intelligent agents (e.g. autonomous vehicles) on the road. This study investigated how a group of pedestrians (crowd) would react to the influence of a slow-moving vehicle. The vehicle's influence was spatially and temporally designed and incorporated into a social force crowd motion model. The proposed model can predict collective pedestrian motion for a couple of seconds in the future. The effectiveness of the proposed model was demonstrated by evaluating the pedestrian motion in fundamental vehicle-pedestrian interaction scenarios. For such scenarios, realistic pedestrian motion trajectories were obtained by conducting controlled experiments. By using the recorded trajectories, the genetic algorithm (GA) was applied to further calibrate the model parameters. The proposed model can successfully describe the pedestrian motion in fundamental vehicle-pedestrian interaction scenarios.

Privacy- and Context-aware Release of Trajectory Data

The availability of large-scale spatio-temporal datasets along with the advancements in analytical models and tools have created a unique opportunity to create valuable insights into managing key areas of society from transportation and urban planning, to epidemiology and natural disasters management. This has encouraged the practice of releasing/publishing trajectory datasets among data owners. However, an ill-informed publication of such rich datasets may have serious privacy implications for individuals. Balancing privacy and utility, as a major goal in the data exchange process, is challenging due to the richness of spatio-temporal datasets. In this paper, we focus on an individual's stops as the most sensitive part of the trajectory and aim to preserve them through spatio-temporal perturbation. We model a trajectory as a sequence of stops and moves, and 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 no safe Point of Interest (POI) can be found on the same route. This hinders the amount of unnecessary distortion since the footprint of the original trajectory is preserved as much as possible. 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 similarity to the original dataset.

All ACM Journals | See Full Journal Index

Search TSAS
enter search term and/or author name