ACM Transactions on

Spatial Algorithms and Systems (TSAS)

Latest Articles

To Buy or Not to Buy: Computing Value of Spatiotemporal Information

Location data from mobile devices is a sensitive yet valuable commodity for location-based services and advertising. We investigate the intrinsic value of location data in the context of strong privacy, where location information is only available from end users via purchase. We present an algorithm to compute the expected value of location data... (more)

A Data-driven Framework for Long-Range Aircraft Conflict Detection and Resolution

At the present time, there is no mechanism for Air Navigation Service Providers (ANSPs) to probe new flight plans filed by the Airlines Operation... (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
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.

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.

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.

Space-Time Drift Point Detection in Mobility Patterns

Location-aware information is now commonplace as the ubiquity and pervasiveness of technology enabled its generation and storage at large scale. These data constitute a rich representation of entities' whereabouts and behavior as they move on the map. Although several studies reported a considerable predictability of such mobility patterns, several factors may impose significant changes on moving behavior. Being able to detect these changes can benefit several applications. In this paper, we formalize and address the problem of detecting mobility drifts on mobility patterns. This problem is particularly challenging due to the noisy and incomplete nature of the data. We design non-parametric tests and present two algorithms to detect mobility drifts when (i) the putative drift point is known in advance; and (ii) there is no previous knowledge about the existence of potential changes and we need to rigorously search for the most likely drift point. To evaluate our algorithms, we perform an extensive experimental study with real-world data coming from a variety of scenarios, such as geo-tagged social media data and GPS traces of connected vehicles. The results show the effectiveness of our algorithms, being able to correctly identify existing drift points on spatial mobility patterns.

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.

Stepping Stone Graph: A Graph for Finding Movement Corridors using Sparse Trajectories

There are many real world applications that require identifying crowd movements such as identifying movement corridors in cities and most popular paths. If one is not given user trajectories 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 answer questions such as shortest paths, most popular paths and movement corridors. A popular graph is the shortest path graph. However the shortest path graph can be inefficient and ineffective for analysing movement data, as it calculates the graph edges considering the shortest paths over all the points in a data set. Therefore, edge sets resulting from shortest path graphs are usually very restrictive and not suitable for movement analysis because of its global view of the data set. We propose the stepping stone graph, which calculates the graph considering point pairs rather than all points, that focuses on possible local movements, making it both efficient and effective for location based social network related data. We demonstrate its uses by applying it in the Location Based Social Network domain and comparing with the shortest path graph. We also compare its properties to a range of other graphs and demonstrate how stepping stone graph relates to Gabriel graph, relative neighbourhood graph and Delaunay triangulation.

All ACM Journals | See Full Journal Index

Search TSAS
enter search term and/or author name