ACM Transactions on

Spatial Algorithms and Systems (TSAS)

Latest Articles

A General Framework for MaxRS and MaxCRS Monitoring in Spatial Data Streams

This article addresses the MaxRS (Maximizing Range Sum) monitoring problem. Given a set of weighted spatial stream objects, this problem is to monitor... (more)

Estimating People Flow from Spatiotemporal Population Data via Collective Graphical Mixture Models

Thanks to the prevalence of mobile phones and GPS devices, spatiotemporal population data can be... (more)

A Layered Approach for More Robust Generation of Road Network Maps from Vehicle Tracking Data

Nowadays, large amounts of tracking data are generated via GPS-enabled devices and other advanced tracking technologies. These constitute a rich... (more)


About TSAS

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. It has a multi-disciplinary perspective spanning a large number of areas where spatial data is manipulated or visualized (regardless of how it is specified - i.e., geometrically or textually), such
as: geography, geographic information systems (GIS), geospatial and spatiotemporal databases, spatial and metric indexing, location-based services, web-based spatial applications, geographic information retrieval (GIR), spatial reasoning and mining, security and privacy, as well as the related visual computing areas of computer graphics, computer vision, geometric modeling, and visualization where the spatial, geospatial, and spatiotemporal data is central.  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
Toward Mining Stop-by Behaviors in Indoor Space

We in this paper explore a new mining paradigm, called \emph{Indoor Stop-by Patterns} (abbreviated as \emph{ISP}), to discover user stop-by behavior in the mall-like indoor environments. The discovery of \emph{ISPs} enables new marketing collaborations, such as a joint coupon promotion, among stores in the indoor spaces (e.g., shopping malls). On the other hand, it can also help in eliminating overcrowding, e.g., crowd control. It is a highly challenging issue, in indoor environments, to retrieve the frequent \emph{ISPs}, especially when the issue of user privacy is highlighted nowadays. To pursue better practicability, we consider the cost-effective wireless sensor-based environment and conduct the analysis of indoor stop-by behavior on real dataset. However, the mining of \emph{ISPs} will face a critical challenge from spatial uncertainty. Previous works on mining indoor movement patterns usually rely on the precise spatio-temporal information by a specific deployment of positioning devices, which cannot be directly applied. In this paper, the proposed \emph{PTkISP} (Probabilistic Top-$k$ Indoor Stop-by Patterns Discovery) framework incorporates the probabilistic model to identify top-$k$ \emph{ISPs} over uncertain dataset collected from the sensing log. Moreover, we develop the uncertain model and devise the IIS (Index 1-itemset) algorithm to enhance the accuracy and efficiency. Our experimental studies show that the proposed \emph{PTkISP} framework can overcome the impact from location uncertainty and efficiently discover high-quality store stop-by patterns, to provide insightful observations for marketing collaborations.

Classification of Passes in Football Matches Using Spatio-temporal Data

A knowledgeable observer of a game of football (soccer) can make a subjective evaluation of the quality of passes made between players during the game. In this paper we consider the problem of producing an automated system to make the same evaluation of passes. We present a model that constructs numerical predictor variables from spatio-temporal match data using feature functions based on methods from computational geometry, and then learns a classification function from labelled examples of the predictor variables. Experimental results show that we are able to produce a classifier with 90.9% accuracy when rating passes as Good, OK or Bad. The agreement between the classifier ratings and the ratings made by a human observer is comparable to the agreement between the ratings made by human observers, and suggests significantly higher accuracy is unlikely to be achieved by a classifier. In addition, we show that the predictor variables computed using methods from computational geometry are among the most important to the learned classifiers.

Grid-Based Method for GPS Route Analysis for Retrieval

Grids are commonly used for presenting spatial data. However, they have not been previously used for analyzing GPS trajectories. Instead, slower and more complicated algorithms based on individual point-pair comparison have been used. We demonstrate how a grid representation can be used to compute four different route measures: novelty, noteworthiness, similarity and inclusion. The measures may be used in several applications such as identifying taxi fraud, automatically updating GPS navigation software, optimizing traffic and identifying commuting patterns. We compare our proposed route similarity measure, C-SIM, to 8 popular alternatives including Edit Distance on Real sequence (EDR) and Frechet distance. The proposed measure is simple to implement and we give a fast, linear time algorithm for the task. It works well under noise, changes in sampling rate and point shifting. We demonstrate that using the grid, a route similarity ranking can be computed in real-time on the Mopsi2014 route dataset which consists of over 6,000 routes. This ranking is an extension of the most similar route search and contains an ordered list of all similar routes from the database. The real-time search is due to indexing the cell database and comes at the cost of spending 80% more memory space for the index. The methods are implemented inside the Mopsi ( route module.

Spatial Partition-based Particle Filtering for Data Assimilation in Wildfire Spread Simulation

Particle Filters (PFs) hold great promise to support data assimilation for spatial temporal simulations to achieve more accurate simulation or prediction results. However, PFs face major challenges to work effectively for complex spatial temporal simulations due to the high dimensional state space of the simulation models, which typically cover large areas and have a large number of spatially dependent state variables. To effectively support data assimilation for large-scale spatial temporal simulations, this paper develops a spatial partition-based particle-filtering framework that breaks the system state and observation data into smaller spatial regions and then carries out localized particle filtering based on these spatial regions. The developed framework exploits the spatial locality property of system state and observation data, and employs the divide-and-conquer principle to reduce state dimension and data complexity. Within this framework, a two-level automated spatial partitioning method is presented to provide automated and balanced spatial partitions with less boundary sensors. The developed framework is applied to a case study of wildfire spread simulations and achieved improved results compared to using standard PFs-based data assimilation methods.


Publication Years 2015-2017
Publication Count 27
Citation Count 14
Available for Download 27
Downloads (6 weeks) 298
Downloads (12 Months) 2387
Downloads (cumulative) 2513
Average downloads per article 93
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)

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

Affiliation Paper Counts
Bangladesh University of Engineering and Technology 1
Rensselaer Polytechnic Institute 1
Montana State University - Bozeman 1
University of Massachusetts Boston 1
Duke University 1
Purdue University 1
University of Osnabruck 1
Swinburne University of Technology 1
University of Texas at San Antonio 1
State University of New York at Albany 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
Academia Sinica Taiwan 1
National University of Singapore 1
Northwestern University 1
University of Hagen 2
Southern Illinois University at Edwardsville 2
Athena Research and Innovation Center in Information, Communication and Knowledge Technologies 2
Pennsylvania State University 2
National Technical University of Athens 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
Texas A and M University System 3
Universite de Versailles Saint-Quentin-en-Yvelines 3
Tulane University 3
University of Wurzburg 3
Federal University of Vicosa 3
Georgia State University 4
Nippon Telegraph and Telephone Corporation 4
University of Southern California 4
George Mason University 4
University of Piraeus 4
University of Melbourne 5

ACM Transactions on Spatial Algorithms and Systems (TSAS) - Regular Papers and SIGSPATIAL Paper

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