ACM Transactions on

Spatial Algorithms and Systems (TSAS)

Latest Articles

Crowd Replication: Sensing-Assisted Quantification of Human Behavior in Public Spaces

A central challenge for public space design is to evaluate whether a given space promotes different types of activities. In this article, as our first contribution, we develop crowd replication as a novel sensor-assisted method for quantifying human behavior within public spaces. In crowd replication, a researcher is tasked with recording the... (more)

Personalized Visited-POI Assignment to Individual Raw GPS Trajectories

Knowledge discovery from GPS trajectory data is an essential topic in several scientific areas, including data mining, human behavior analysis, and... (more)

Fast Computation of Clustered Many-to-many Shortest Paths and Its Application to Map Matching

We examine the problem of computing shortest paths in a transportation network from a set of geographically clustered source nodes to a set of target... (more)

From Rocks to Pebbles: Smoothing Spatiotemporal Data Streams in an Overlay of Sensors

Spatiotemporal streams are prone to data quality issues such as missing, duplicated and delayed data—when data generating sensors malfunction, data transmissions experience problems, or when data are stored or processed improperly. However, many important real-time applications rely on the continuous availability of stream values, e.g., to... (more)

Spatial Auto-regressive Dependency Interpretable Learning Based on Spatial Topological Constraints

Spatial regression models are widely used in numerous areas, including detecting and predicting... (more)

Activity-aware Ridesharing Group Trip Planning Queries for Flexible POIs

In recent years, ridesharing has become a popular model that enables users to share their rides with others. In this article, we introduce a novel... (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.

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.

In-Route Task Selection in Spatial Crowdsourcing

Consider a road network and a worker who is traveling on a given path between points s and d (e.g., from school to home). Consider further that there is a set of tasks to be performed, where each completed task yields a reward, and, finally, that the worker has an upper-bound for the total travel distance. We call this problem, the In-Route Task Selection (IRTS) problem and consider two variants thereof. In IRTS-PP the worker has a preferred path PP from s to d and wants to travel along PP for as long as possible. In IRTS-SP the worker only specifies s and d and he/she wants to deviate as little as possible from the shortest path connecting s and d. The former may be interesting to workers when paths other than the shortest one are more desirable, e.g., due to perceived safety. We investigate both IRTS variants using the skyline paradigm in order to obtain the set of non-dominated solutions w.r.t. the trade-offs between earned rewards and detour. This is practically relevant as it empowers the worker allowing him/her to decide, at query time, which tasks suit him/her better. Both variants of the IRTS problem are NP-hard. We propose an exact solution that serves as a benchmark, it does not scale to large sized IRTS instances. Our proposed heuristic approaches, on the other hand, can solve realistic IRTS instances of large sizes often in sub-second query processing time, still producing approximate skyline sets with good quality.

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.

RegRocket: Scalable Multinomial Autologistic Regression with Unordered Categorical Variables Using Markov Logic Networks

Autologistic regression is one of the most popular statistical tools to predict spatial phenomena in several applications including epidemic diseases detection, species occurrence prediction, earth observation and business management. In general, autologistic regression divides the space into a two-dimensional grid, where the prediction is performed at each cell in the grid. The prediction at any location is based on a set of predictors (i.e., features) at this location and predictions from neighboring locations. In this paper, we address the problem of building efficient autologistic models with multi-nomial (i.e., categorical) prediction and predictor variables. Unfortunately, existing methods to build autologistic models are designed for binary variables in addition to being computationally expensive. Therefore, we introduce RegRocket; a scalable framework to build multi-nomial autologistic models for predicting large-scale spatial phenomena. RegRocket considers both the accuracy and efficiency aspects when learning the regression model parameters. To this end, RegRocket is built on top of Markov Logic Network (MLN), a scalable statistical learning framework, where its internals and data structures are optimized to process spatial data. RegRocket provides an equivalent representation of the multi-nomial prediction and predictor variables using MLN where the dependencies between these variables are transformed into first-order logic predicates. Then, RegRocket employs an efficient framework that learns the model parameters from the MLN representation in a distributed manner. Extensive experimental results based on two large real datasets show that RegRocket can build multi-nomial autologistic models, in few minutes, for 1 million grid cells with 89% average accuracy.

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