ACM Transactions on

Spatial Algorithms and Systems (TSAS)

Latest Articles

Detecting Deviations from Intended Routes Using Vehicular GPS Tracks

This article proposes a method to find intersections at which cars tend to deviate from the optimal route based on global positioning system (GPS)... (more)

The Medial Axis of a Multi-Layered Environment and Its Application as a Navigation Mesh

Path planning for walking characters in complicated virtual environments is a fundamental task in simulations and games. A navigation mesh is a data... (more)

Enhanced Indexing and Querying of Trajectories in Road Networks via String Algorithms

In this article, we propose a novel indexing and querying method for trajectories constrained in a road network. We aim to provide efficient... (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 its inaugural issue. Please use manuscriptcentral ( to submit articles, check the status of articles and for reviewing tasks.

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

Nowadays people can access LBSs as a group via mobile devices to plan their daily activities with friends and relatives. In this paper, we introduce an important class of group oriented LBSs, group optimal accessible location (GOAL) queries that enable users to identify the location of a point of interest (POI) that has the minimum total distance to a given set of paths. GOAL queries have many applications such as the selection of an optimal location for group meet-ups or for a mobile facility such as a food truck. In a GOAL query, each trip or path is represented as a set of line segments and the distance of a POI from a path is computed as the minimum distance of the POI to any line segment of the path. We develop an efficient approach to evaluate GOAL queries. The novelty of our GOAL query processing algorithm in contrast to other spatial query processing algorithms is the reformulation of a GOAL query by considering only a subset of path segments from the given set of paths, which is also the key ingredient behind the efficiency of our proposed algorithm. We exploit geometric properties and develop pruning techniques to eliminate both POIs and path segments that cannot provide the optimal solution for a GOAL query. Our experimental results demonstrate that we provide a readily deployable solution for real-life applications.

Feature-based Map Matching for Low-Sampling-Rate GPS Trajectories

With the increasing availability of GPS-equipped mobile devices, location-based services have become an integral part of people's everyday life. Among one of the initial steps of positioning data management, map matching aims to reduce the uncertainty in a trajectory by matching the GPS points to the road network on a digital map. Most existing work has focused on estimating the likelihood of a candidate path based on the GPS observations, while neglecting to model the probability of a route choice from the perspective of drivers. Here we propose a novel feature-based map matching algorithm that estimates the cost of a candidate path based on both GPS observations and human factors. To take human factors into consideration is very important especially when dealling with low sampling rate data where most of the movement details are lost. Additionally, we simultaneously analyze a sebsequence of coherent GPS points by utilizing a new segment-based probabilistic map matching strategy, which is less susceptible to the noiseness of the positioning data. We have evaluated both the offline and the online versions of our proposed approach on a public large-scale GPS dataset, which consists of 100 trajectories distributed all over the world. The experimental results show that our method is robust to sparse data with large sampling intervals (e.g., 60 s - 300 s) and challenging track features (e.g., u-turns and loops). Our method obtains the state-of-the-art map matching accuracy with a competitive processing time compared with existing map matching approaches.

Weighted Aggregate Reverse Rank Queries

In marketing, helping manufacturers to find the matching preferences of potential customers for their products is an essential work especially in e-commerce analyzing with big data. The aggregate reverse rank query has been proposed to return top-$k$ customers who regard a given product bundling as highest aggregate rank than other customers, where the aggregate rank is defined as the sum of each product's rank. This query correctly reflects the request only when the customers consider the products in the product bundling equally. Unfortunately, rather than thinking products equally, in most cases, people buy a product bundling because they appreciate a special part of the bundling. Manufacturers, such as video games companies and cable television industries, are also willing to bundle some attractive products with less popular products for the purpose of maximum benefits or inventory liquidation. Inspired by the necessity of general aggregate reverse rank query for unequal thinking, we propose a weighted aggregate reverse rank query which treats the elements in product bundling with different weights to target customers from all aspects of thought. To solve this query efficiently, we first try a straightforward extension. Then we re-build the bound-and-filter framework for the weighted aggregate reverse rank query. We prove theoretically that the new approach finds the optimal bounds and develops the maximum efficient algorithm based on this bounds. The theoretical analysis and experimental results demonstrated the efficacy of the proposed methods.

CellNet: Inferring road networks from GPS trajectories

Road networks are essential nowadays, especially for people travelling to large, unfamiliar cities. Moreover, cities are constantly growing and road networks need periodical updates to provide reliable information. We propose an automatic method to generate the road network using a GPS trajectory dataset. The method, titled CellNet, works by first detecting the intersections (junctions) using a clustering-based technique and then creating the road segments in-between. We compare CellNet against three conceptually different state-of-the-art alternatives. The results show that CellNet provides better accuracy and is less sensitive to parameter setup. The generated road network occupies only 25% of the memory required for the networks produced by other methods.

Disk-Based Indexing of Recent Trajectories

The plethora of location-aware devices has led to countless location-based services in which huge amounts of spatio-temporal data get created every day. Several applications require efficient processing of queries on the locations of moving objects over time, i.e., the moving object trajectories. This calls for efficient trajectory-based indexing methods that capture both the spatial and temporal dimensions of the data in a way that minimizes the number of disk I/Os required for both updating and querying. Most existing spatio-temporal index structures capture either the current locations of the moving objects or the entire history of the moving objects. Historical spatio-temporal indexing methods require multiple disk I/Os to process new updates, and use a discrete trajectory representation that may result in incomplete query results. In this paper, we introduce the trails-tree, a disk-based data structure for indexing recent trajectories. The trails-tree requires half the number of disk I/Os needed by other historical spatio-temporal indexing methods. We give a detailed description of the trails-tree, and we mathematically analyze its performance. Moreover, we present a novel query processing algorithm that ensures the completeness of the query resultset. We experimentally verify the performance of the trails-tree using various real and synthetic datasets.

Hierarchical Spatial Aggregation for Level-of-Detail Visualization of 3D Thematic Data

The visualization of georeferenced thematic data by virtual environments represents a key functional requirement in a large number of geo-information applications and systems. The perception of large, detailed thematic data sets, however, can be inhibited by visual clutter and information overload, especially in case of three-dimensional data. Level-of-detail visualization techniques can mitigate these issues and guide the viewers in their analyses. While the commonly used geometric level-of-detail techniques can reduce the complexity of the data's reference geometry, they generally do not take into account thematic data. This article presents two spatial aggregation techniques for generating level-of-detail representations for thematic data: The scene-based technique aggregates data solely based on spatial locations, thus supporting visual analysis of data with arbitrary reference geometry. The object-based technique performs aggregation based on scene-specific objects and their hierarchy to facilitate per-object analysis. Both techniques operate in real-time during rendering to support on-the-fly and on-demand level-of-detail generation for the visualization of spatiotemporal data sets. We demonstrate the application of both techniques using real-world data sets, including solar potential analyses and the propagation of pressure waves in a virtual city model.

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 empirical study, we investigate the geographical characteristics of the Internet as well as examine the relation between geography and intra-AS and inter-AS routing policies. We show that the ingress-to-egress subpaths have lower circuitousness compared to the end-to-end paths. Our findings not only demonstrate the efficient backbone infrastructures deployed by ASes but also show the consequences of economical incentives on the adoption of inter-AS paths. We present and examine the existence of a strong correlation between the geographical distance and round trip delay time as well as the lack of a correlation between the geographical distance and hop length in the Internet. We investigate the relation between the geographical distance and intra-AS routing policies by employing cross-AS Internet topology maps. Our results show that more than two thirds of the intra-AS subpaths are congruent with the shortest geographical distance whether or not the geographical distance is employed as a parameter in routing decisions. Our results provide new insights into the relations between geography and Internet routing which allow the network researchers and practitioners to improve their networking infrastructures, reevaluate their routing policies, deploy geography-aware network overlays and develop more realistic network simulation processes.

2D Vector Map Fragile Watermarking with Region Location

Several existing 2D vector map fragile watermarking methods cannot locate all the regions affected by tampering. Once these tampered regions are detected as untampered, some misuses of the vector map data may be caused. In this paper, we propose a fragile watermarking framework that locates regions of tampered spatial features. In particular, we propose dividing the features of the host vector map into groups, and embedding a watermark consisting of location-bits and check-bits into each group. On the receiver side, by comparing the extracted and calculated check-bits, one can identify the tampered groups and their current regions. Then the location-bits extracted from the mapping groups are used to indicate the original regions of the tampered groups. We demonstrate and analyze the applicability of this framework by instantiating it with a simulated annealing (SA) based group division method, a minimum encasing rectangle (MER) based location-bits generation method and an existing reversible data hiding method. The experimental results show that the proposed framework can locate the regions influenced by tampering, and the SA based group division method can get a better region location accuracy.

Identifying surrounds and engulfs relations in mobile and coordinate-free geosensor networks

This paper concerns the definition and identification of qualitative spatial relationships for the full and partial enclosure of spatial regions. The paper precisely defines three relationships between regions, surrounds, engulfs, and envelops, highlighting the correspondence to similar definitions in the literature. An efficient algorithm capable of identifying these qualitative spatial relations in a network of dynamic (mobile) geosensor nodes is developed and tested. The algorithms are wholly decentralized, and operate in-network with no centralized control. The algorithms are also coordinate-free, able to operate in distributed spatial computing environments where coordinate locations are expensive to capture or otherwise unavailable. Experimental evaluation of the algorithms designed demonstrates the efficiency of the approach. Although the algorithm communication complexity is dominated by an overall worst-case O(n2) leader election algorithm, the experiments show in practice an average-case complexity approaching linear, O(n1.1).


Publication Years 2015-2018
Publication Count 40
Citation Count 26
Available for Download 40
Downloads (6 weeks) 308
Downloads (12 Months) 2422
Downloads (cumulative) 6358
Average downloads per article 159
Average citations per article 1
First Name Last Name Award
Pankaj Agarwal ACM Fellows (2002)
Elisa Bertino ACM Fellows (2003)
Chang-Tien Lu ACM Distinguished Member (2015)
Timoleon Sellis ACM Fellows (2013)
ACM Senior Member (2008)
Cyrus Shahabi ACM Distinguished Member (2009)
Ouri Wolfson ACM Fellows (2001)
Moustafa Amin Youssef ACM Distinguished Member (2015)
Roger Zimmermann ACM Distinguished Member (2017)

First Name Last Name Paper Counts
Dieter Pfoser 3
Dimitrios Skoutas 2
Maria Damiani 2
Rafal Angryk 2
Lars Kulik 2
Timos Sellis 2
Petrus Martens 2
Berkay Aydin 2
Pasi Fränti 1
Kyle Hickmann 1
Carola Wenk 1
Pankaj Agarwal 1
Salles Magalhães 1
Fabio Valdés 1
Masaaki Iiyama 1
Michihiko Minoh 1
Wouter Meulemans 1
Mauro Negri 1
Benedikt Budig 1
Wei Niu 1
Ouri Wolfson 1
Alexandros Belesiotis 1
Alexandros Efentakis 1
Joël Estephan 1
Joachim Gudmundsson 1
Hitoshi Shimizu 1
Cyrus Shahabi 1
Alex Beutel 1
Bettina Speckmann 1
Peter Scheuermann 1
Feng Chen 1
Shane Culpepper 1
Wangchien Lee 1
Karthik Pillai 1
Juan Banda 1
Stylianos Sideridis 1
Weishinn Ku 1
Yuan Long 1
Tomoharu Iwata 1
Naonori Ueda 1
Martin Nöllenburg 1
Elisa Bertino 1
Yi Yu 1
Takayoshi Yoshimura 1
Wouter Van Toll 1
Preeti Goel 1
Sara Migliorini 1
Chung Kuo 1
Nikos Pelekis 1
Shanyun Teng 1
Michael Horton 1
Claudio Silvestri 1
Marcus Andrade 1
Sadao Obana 1
Karine Zeitouni 1
Atlas Iv 1
Marc Van Kreveld 1
André Van Renssen 1
Liang Zhao 1
Daniel Ayala 1
Jie Lin 1
Farhana Choudhury 1
Denian Yang 1
Daichi Amagata 1
Takahiro Hara 1
Futoshi Naya 1
M Robles-Ortega 1
Leyla Kazemi 1
Mark Mckennney 1
Andreas Gemsa 1
Jan Haunert 1
Thomas Mølhave 1
Chaulio Ferreira 1
Georgios Skoumas 1
Suhua Tang 1
Janne Kovanen 1
Yukihiro Tadokoro 1
Mikihiko Mori 1
Yoshiharu Ishikawa 1
Takumi Fujino 1
Atsushi Hashimoto 1
Mohammed Ali 1
Sarana Nutanong 1
Thomas Van Dijk 1
Bo Xu 1
Heba Aly 1
Moustafa Youssef 1
Sophia Karagiorgou 1
Lidia Ortega 1
Hien To 1
Roger Frye 1
Gabriel Ghinita 1
Ralf Güting 1
Kotagiri Ramamohanarao 1
Egemen Tanin 1
Giuseppe Pelagatti 1
Alexander Wolff 1
Zhifeng Bao 1
Huiju Hung 1
Christodoulos Efstathiades 1
Dustin Kempton 1
Anas Basalamah 1
Kunta Chuang 1
Sanjay Chawla 1
Mahmuda Ahmed 1
Brittany Fasy 1
Anastasios Kyrillidis 1
Dai That 1
Sanjay Purushotham 1
Changtien Lu 1
Naren Ramakrishnan 1
Bhaskar DasGupta 1
George Papadakis 1
Panagiotis Tampakis 1
Xiaolin Hu 1
Radu Mariescu-Istodor 1
Ahmet Küçük 1
Francisco Feito 1
Wm Franklin 1
Roger Zimmermann 1
Tapani Sarjakoski 1
Iulian Popa 1
Roland Geraerts 1
Satoshi Koide 1
Chuan Xiao 1
Hidekazu Kasahara 1
Kevin Buchin 1
Alberto Belussi 1
Zhijiao Liu 1
James Caverlee 1
Yannis Theodoridis 1

Affiliation Paper Counts
Microsoft Corporation 1
City University London 1
Northwestern University 1
Umm Al Qura University 1
State University of New York at Albany 1
Rensselaer Polytechnic Institute 1
Carnegie Mellon University 1
Ca' Foscari University of Venice 1
Bangladesh University of Engineering and Technology 1
University of Maryland 1
National University of Singapore 1
Academia Sinica Taiwan 1
Hosei University 1
Purdue University 1
University of Hawaii at Manoa 1
Montana State University - Bozeman 1
University of Texas at Austin 1
Stanford University 1
Auburn University 1
City University of Hong Kong 1
Hamad bin Khalifa University 1
University of Texas at San Antonio 1
Osnabruck University 1
Duke University 1
University of Athens 1
University of Massachusetts Boston 1
Virginia Tech 2
University of Milan 2
Athena Research and Innovation Center in Information, Communication and Knowledge Technologies 2
Eindhoven University of Technology 2
Karlsruhe Institute of Technology 2
University of Verona 2
University of Hagen 2
Politecnico di Milano 2
Osaka University 2
University of Electro-Communications 2
National Technical University of Athens 2
National Cheng Kung University 2
Swinburne University of Technology 2
Southern Illinois University at Edwardsville 2
University of Eastern Finland 2
Research Organization of Information and Systems National Institute of Informatics 2
Pennsylvania State University 2
Texas A and M University System 3
Federal University of Vicosa 3
University of Illinois at Chicago 3
Universidad de Jaen 3
The University of Sydney 3
RMIT University 3
Nagoya University 3
Tulane University 3
Utrecht University 3
Universite de Versailles Saint-Quentin-en-Yvelines 3
University of Wurzburg 3
Kyoto University 4
University of Piraeus 4
University of Southern California 4
Nippon Telegraph and Telephone Corporation 4
George Mason University 4
University of Melbourne 5
Georgia State University 10

ACM Transactions on Spatial Algorithms and Systems (TSAS)

Volume 4 Issue 1, June 2018
Volume 3 Issue 4, May 2018

Volume 3 Issue 3, November 2017
Volume 3 Issue 2, August 2017 SIGSPATIAL Paper and Regular Papers
Volume 3 Issue 1, May 2017 Regular Papers and SIGSPATIAL Paper

Volume 2 Issue 4, November 2016 Regular Papers and SIGSPATIAL Paper
Volume 2 Issue 3, October 2016
Volume 2 Issue 2, July 2016 Invited Papers from ACM SIGSPATIAL
Volume 2 Issue 1, April 2016

Volume 1 Issue 2, November 2015
Volume 1 Issue 1, August 2015 Inaugural Issue
All ACM Journals | See Full Journal Index

Search TSAS
enter search term and/or author name