ACM Transactions on

Spatial Algorithms and Systems (TSAS)

Latest Articles

Efficient Computation of the Optimal Accessible Location for a Group of Mobile Agents

Nowadays, people can access location-based services (LBSs) as a group via mobile devices to plan their daily activities with friends and relatives. In... (more)

Geography and Routing in the Internet

The Internet is a network of networks consisting of tens of thousands of Autonomous Systems (ASes). These ASes connect to each other in different forms to enable the “global” Internet communication. In this study, we investigate the geographical characteristics of the visible Internet as well as examine the relation between... (more)

2D Vector Map Fragile Watermarking with Region Location

Locating the original region of tampered features is a challenging task for existing 2D vector map fragile watermarking methods. This article presents... (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
Personalized Travel Time Prediction using a Small Number of Probe Vehicles

Predicting the travel time of a path is an important task in route planning and navigation applications. As more GPS floating car data has been collected to monitor urban traffic, GPS trajectories of floating cars have been frequently used to predict path travel time. However, most trajectory-based methods rely on deploying GPS devices and collect real-time data on a large taxi fleet, which can be expensive and unreliable in smaller cities. This work deals with the problem of predicting path travel time when only a small number of GPS floating cars are available. We developed an algorithm that learns local congestion patterns of a compact set of frequently shared paths from historical data. Given a travel time prediction query, we identify the current congestion patterns around the query path from recent trajectories, then infer its travel time in the near future. Driver identities are also used in predicting personalized travel time. Experimental results using 10-25 taxis in urban areas of Shenzhen, China show that personal prediction has on average 3.4 minutes of error on trips of 10-65 minutes. This result improves the baseline approach of using purely historical trajectories by 16.8% on average, over four regions with various degree of path regularity. It also outperforms a state-of-the-art travel time prediction method that uses both historical trajectories and real-time trajectories.

Dictionary Compression in Point Cloud Data Management

Nowadays, massive amounts of point cloud data can be collected thanks to advances in data acquisition and processing technologies like dense image matching and airborne LiDAR scanning. With the increase in volume and precision, point cloud data offers a useful source of information for natural resource management, urban planning, self-driving cars and more. At the same time, the scale at which point cloud data is produced, introduces management challenges: it is important to achieve efficiency both in terms of querying performance and space requirements. Traditional file-based solutions to point cloud management offer space efficiency, however, cannot scale to such massive data and provide the declarative power of a DBMS. In this paper, we propose a time- and space-efficient solution to storing and managing point cloud data in main memory column-store DBMS. Our solution, Space-Filling Curve Dictionary-Based Compression (SFC-DBC), employs dictionary-based compression in the spatial data management domain and enhances it with indexing capabilities by using space-filling curves. SFC-DBC does so by constructing the space-filling curve over a compressed, artificially introduced dictionary space. Consequently, SFC-DBC significantly optimizes query execution, and yet does not require additional storage resources, compared to traditional dictionary-based compression. With respect to space-filling curve-based approaches, it minimizes storage footprint and increases resilience to skew. As a proof of concept, we develop and evaluate our approach as a research prototype in the context of SAP HANA. SFC-DBC outperforms other dictionary-based compression schemes by up to 61% in terms of space and up to 9.4x in terms of query performan

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

Public spaces serve an important role in contemporary cities, providing a medium for passive and active engagement and a place for discovery and reflection. A central challenge for public space design is to evaluate whether a given space indeed promotes the desired activities. In this paper, we contribute by developing crowd replication as a novel sensor-assisted method for quantifying human behavior within public spaces. The idea in crowd replication is to task a researcher with replicating the behavior of people using a space while being instrumented with a mobile device that captures a sensor trace of the replicated behaviors. Through mathematical modeling, behavioral indicators extracted from the replicated trajectories can be extrapolated to represent a larger population. We develop the overall method, and propose a novel pedestrian sensing solution for capturing high-quality information about human behavior within public spaces. We validate our approach through a case study carried out within a representative example of a metropolitan-scale public space. Our results show that crowd-replicated data closely mirrors the real human dynamics in public spaces and provides a useful building block for human-scale analytics. We also demonstrate that crowd replication can reduce overall data collection efforts while producing high quality and unbiased data about the behaviors and activities of people within the space. Finally, we demonstrate that our pedestrian sensing solution enables crowd replication to cost-effectively capture fine-grained and detailed indicators of liveliness, extent of social interaction, and other factors congruent with the common understandings about the qualities of public spaces.

Flood Risk Analysis on Terrains

An important problem in terrain analysis is modeling how water flows across a terrain and creates floods by filling up depressions. In this paper we study the \emph{flooding query} problem: Preprocess a given terrain $\terrain$, represented as a triangulated $xy$-monotone surface with $n$ vertices, into a data structure so that for a query rain region $\varregion$ and a query point $q$ on $\terrain$, one can quickly determine how much rain has to fall in $\varregion$ so that $q$ is flooded. Available terrain data is often subject to uncertainty which must be incorporated into the terrain analysis. By representing the uncertainty in the terrain data explicitly, we can develop methods for flood risk analysis that properly incorporate terrain uncertainty when reporting what areas are at risk of flooding. We present two results. First, we present an $\BigO(n\log{n})$-time algorithm for preprocessing $\terrain$ with a linear-size data structure that can answer a flooding query in $\BigO(|\varregion|+\varrainpoints \log n)$ time, where $|\varregion|$ is the number of vertices in $\varregion$, $\varrainpoints$ is the number of minima of the terrain at which rain is falling, and $n$ is the number of vertices of the terrain. Next, we extend this data structure to handle ``uncertain'' terrains, using a standard Monte Carlo method. Given a probability distribution on terrain data, our data structure returns the probability of a query point being flooded if a specified amount of rain falls on a query region.

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 from a user, without access to the specific coordinates of the location data point. We use decision-theoretic techniques to provide a principled way for a potential buyer to make purchasing decisions about private user location data. We illustrate our approach in three scenarios: the delivery of targeted ads specific to a user?s home location, the estimation of traffic speed, and location prediction. In all three cases, the methodology leads to quantifiably better purchasing decisions than competing methods.

Congestion-Aware Ride-Sharing

In its current form, ride-sharing is responsible for a small fraction of traffic load compared to other transportation modes, especially private vehicles. As its benefits became more evident, and obstacles, e.g., lack of liability legislation, that may hinder its larger scale adoption are being overcome, ride-sharing will be a more common mode of transportation. In particular, autonomous vehicles (AVs) are showing their proficiency on the roads, which may also catalize ride-sharing ubiquity. For example, while an AV owner is at work, he may find appealing to offer his AV as a service or rent it to Uber so that the vehicle serves others? transportation requests. Furthermore, this disruptive technology is backed up by companies like Google (Waymo), Tesla and Uber. Therefore, ride-sharing will soon become a source of traffic congestion itself. In this paper, we present an efficient congestion-aware ride-sharing algorithm which, instead of finding optimal travel plans based on traffic load generated by other means of transportation, it computes optimal travel plans for thousands of ride-sharing requests within a time interval. Note that in this problem, an optimal travel plan for a group of requests may affect an already computed travel plan for another concurrent group of requests, therefore plans cannot be isolated from each other.

Personalized Visited-POI Assignment to Individual Raw GPS Trajectories

Knowledge discovery from GPS trajectory data is an important topic in several areas including data mining, human behavior analysis, and user modeling. This paper proposes a task that assigns personalized visited-POIs. Its goal is to estimate fine-grained and pre-defined locations (i.e., points of interest (POI)) that a user actually visits and assign the visited location information to the corresponding span of the users (personal) GPS trajectories. We also introduce a novel algorithm to solve this assignment task. First, we exhaustively extract stay points as candidates for significant locations using a variant of a conventional stay-point extraction method. Then we select true significant locations and simultaneously assign visited-POIs to them by considering various aspects, which we formulate in integer linear programming. Experimental results conducted on an actual user dataset show that our method achieves higher accuracy in the visited-POI assignment task than the various cascaded procedures of conventional methods.

All ACM Journals | See Full Journal Index

Search TSAS
enter search term and/or author name