ACM Transactions on

Spatial Algorithms and Systems (TSAS)

Latest Articles

Grid-Based Method for GPS Route Analysis for Retrieval

Grids are commonly used as histograms to process spatial data in order to detect frequent patterns, predict destinations, or to infer popular places.... (more)

Measuring the Significance of Spatiotemporal Co-Occurrences

Spatiotemporal co-occurrences are the appearances of spatial and temporal overlap relationships among trajectory-based spatiotemporal instances with... (more)

Efficient Visibility Determination in Urban Scenes Considering Terrain Information

In this article, we introduce a novel occlusion culling method working on the server side to provide real-time navigation on web-based systems.... (more)


ACM Transactions on Spatial Algorithms and Systems (TSAS) is a new scholarly journal that publishes high-quality papers on all aspects of spatial algorithms and systems and closely related disciplines. READ MORE

Call-for-nominations: ACM TSAS has issued a call for nominations for its next editor in chief.  The deadline for submitting nominations is March 31, 2018.

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
Batch processing of Top-k Spatial-textual Queries

Several indexing techniques have been proposed to efficiently answer top-k spatial-textual queries in the last decade. However, all of these approaches focus on answering one query at a time. In contrast, how to design efficient algorithms that can exploit similarities between incoming queries to improve performance has received little attention. In this paper, we study a series of efficient approaches to batch process multiple top-k spatial-textual queries concurrently. We carefully design a variety of indexing structures for the problem space by exploring the effect of prioritizing spatial and textual properties on system performance. Specifically, we present an efficient traversal method, SF-SEP over an existing space-prioritized index structure. Then, we propose a new space-prioritized index structure, the MIR-Tree to support a filter-and-refine based technique, SF-GRP. To support the processing of text-intensive data, we propose an augmented, inverted indexing structure that can easily be added into existing text search engine architectures, and a novel traversal method for batch processing of the queries. In all of these approaches, the goal is to improve the overall performance by sharing the I/O costs of similar queries. Finally, we demonstrate significant I/O savings in our algorithms over traditional approaches by extensive experiments on three real datasets, and compare how properties of different datasets affect the performance. Many applications in streaming, micro-batching of continuous queries, and privacy-aware search can benefit from this line of work.

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

We propose a novel indexing and querying method for trajectories constrained in a road network. We aim to provide efficient algorithms for various types of spatio-temporal queries that involve routing in road networks such as 1) finding moving objects that have traveled along a given path during a given time interval, 2) extracting all paths traveled after a given spatio-temporal context, 3) enumerating all paths between two locations traveled during a certain time interval. Unlike the existing methods in spatial database research, we employ indexing techniques and algorithms from string processing. This idea is based on the fact that we can represent spatial paths as strings, because trajectories in a network are represented as sequences of road segment IDs. The proposed SNT-index introduces two novel concepts to trajectory indexing. The first is FM-index, a compact in-memory data structure for pattern matching. The second is an inverse suffix array, which allows the FM-index to be integrated with the temporal information stored in a forest of B+-trees. Thanks to these concepts, we can reduce the number of B+-tree accesses required by the query processing algorithms to a constant number, something that cannot be achieved with existing methods. Although an FM-index is essentially a static index, we also propose a practical method of appending new data to the index. Finally, experiments show that our method can process the target queries for more than one million trajectories in a few tens of milliseconds, which is significantly faster than the baseline algorithms without string algorithms.

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. In this paper, we present an improved definition of the Explicit Corridor Map (ECM), a navigation mesh that allows efficient path planning and crowd simulation for disk-shaped characters of any radius. The ECM is a medial axis (MA) annotated with nearest-obstacle information. For a 2D environment with n obstacle vertices, the ECM has size O(n) and can be computed in O(n log n) time. In 3D spaces, characters are constrained to walkable surfaces which form the walkable environment (WE). This can be converted to a multi-layered environment (MLE) in which multiple planar layers are connected by line segment connections. Typical real-world examples are multi-storey buildings, train stations, and sports stadiums. We define the medial axis and the ECM for multi-layered environments, based on projected distances on the ground plane. For an MLE with n obstacle points and k connections, the MA has size O(n). We present an improved algorithm that constructs the MA and ECM in O(n log n log k) time. Our implementations show that the ECM can be computed efficiently for large 2D and multi-layered environments, and that it can be used to compute paths within milliseconds. This enables simulations of large virtual crowds of heterogeneous characters in real-time.

Analyzing and Predicting Spatial Crime Distribution Using Crowdsourced and Open Data

Data analytics has a significantly increasing impact on tackling various societal challenges. In this paper, we investigate how information from several heterogeneous and publicly available sources can be used to discover insights and make predictions about the spatial distribution of crime in large urban environments, thus contributing to the safety of citizens. A series of important research questions is addressed. First, we examine how useful different types of data are for the task of crime levels prediction, focusing especially on how prediction accuracy can be improved by combining data from multiple information sources. Then, we look into individual features, aiming to identify and quantify the most important factors. Finally, we drill down to different crime types, elaborating on how the prediction accuracy and the importance of individual features vary across them. Our analysis involves 6 different datasets, from which more than 3,000 features are extracted, filtered, and used to learn models for predicting crime rates across 11 different crime categories. Our results indicate that combining data from multiple information sources can significantly improve prediction accuracy. They also highlight which features affect prediction accuracy the most, as well as for which particular crime categories the predictions are more accurate.

Spatio-temporal Matching for Urban Transportation Applications

In this paper we present a search problem in which mobile agents are searching for static resources. Each agent wants to obtain exactly one resource. Both agents and resources are spatially located on a road network and the movement of the agents is constrained to the road network. This problem applies to various transportation applications including: vehicles (agents) searching for parking (resources) and taxicabs (agents) searching for clients to pick up (resources). In this work, we design search algorithms for such scenarios. We model the problem in different scenarios that vary based on the level of information that is available to the agents. These scenarios vary from: scenarios in which agents have complete information about other agents and resources, to scenarios in which agents only have access to a fraction of the data about the availability of resources (uncertain data). We also propose pricing schemes that incentivize vehicles to search for resources in a way that benefits the system and the environment. Our proposed algorithms were tested in a simulation environment that uses real-world data. We were able to attain up to 40% improvements over other approaches that were tested against our algorithms.

Detecting Deviations from Intended Routes Using Vehicular GPS Tracks

This study proposes a method to find intersections at which many cars deviate from optimal routes using global positioning system (GPS) tracking data. Such deviations indicate that on-road navigation aids, such as car navigation systems (CNS) and road signage, are not readily available. For continuous improvement of on-road navigation, developing a method to automatically find intersections with high deviation rates is an important task. If all destinations in a drive are known, deviations can be enumerated as a difference in the optimal route that goes through all the destinations and the actual GPS data; however, such a set of destinations are not always queried to CNSs and the optimal route is unknown. To estimate deviation rates without knowing such destinations, we divides the GPS tracks into sets of sub-sequences, and consider the optimal route from the start to the end of sub-sequence. An approximate deviation rate is estimated by enumerating differences in the optimal route and the actual GPS data over all sub-sequences. We applied the proposed method to 3,843 GPS tracks collected from visitor drivers in Kyoto city. Thresholding the estimated deviation rate yielded 39 intersections from 14,543 candidates. The results showed a certain level of correlation between the obtained deviations and rerouting locations from actual CNS data. We also found several intersections where faulty route suggestions are provided by CNSs.


Publication Years 2015-2017
Publication Count 34
Citation Count 24
Available for Download 34
Downloads (6 weeks) 242
Downloads (12 Months) 2396
Downloads (cumulative) 3735
Average downloads per article 110
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)
Moustafa Amin Youssef ACM Distinguished Member (2015)
Roger Zimmermann ACM Distinguished Member (2017)

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

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

ACM Transactions on Spatial Algorithms and Systems (TSAS)

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