ACM Transactions on

Spatial Algorithms and Systems (TSAS)

Latest Articles

Location Estimation Using Crowdsourced Spatial Relations

The “crowd” has become a very important geospatial data provider. Specifically, nonexpert users have been providing a wealth of... (more)

An Efficient External Memory Algorithm for Terrain Viewshed Computation

This article presents TiledVS, a fast external algorithm and implementation for computing viewsheds. TiledVS is intended for terrains that are too... (more)


With modern focus on remote sensing technology, such as LiDAR, the amount of spatial data, in the form of massive point clouds, has increased dramatically. Furthermore, repeated surveys of the same areas are becoming more common. This trend will only increase as topographic changes prompt surveys over already scanned areas, in which case we obtain... (more)

Protecting Against Velocity-Based, Proximity-Based, and External Event Attacks in Location-Centric Social Networks

Mobile devices with positioning capabilities allow users to participate in novel and exciting... (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, solid 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.

New options for ACM authors to manage rights and permissions for their work

ACM introduces a new publishing license agreement, an updated copyright transfer agreement, and a new author-pays option which allows for perpetual open access through the ACM Digital Library. For more information, visit the ACM Author Rights webpage.

Forthcoming Articles
Social Influence-Aware Reverse Nearest Neighbor Search

Business location planning, critical to success of many businesses, can be addressed by reverse nearest neighbors (RNN) query using geographical proximity to the customers as the main metric to find a store location which is the closest to many customers. Nevertheless, we argue that other marketing factors such as social influence could be considered in the process of business location planning. In this paper, we propose a framework for business location planning that takes into account both factors of geographical proximity and social influence. An essential task in this framework is to compute the influence spread of RNNs for candidate locations. To alleviate the excessive computational overhead and long latency in the framework, we trade storage overhead for processing speed by pre-computing and storing the social influences between pairs of customers. Based on Targeted Region-oriented and RNN-oriented processing strategies, we develop two suites of algorithms that incorporate various efficient ordering and pruning techniques to enhance our framework. Experiments validate our ideas and evaluate the efficiency of the proposed algorithms over various parameter settings.

Personalized Group Recommender Systems for Location and Event Based Social Networks

Location-Based Social Networks (LBSNs) such as Foursquare, Google+ Local, etc., and Event-Based Social Networks (EBSNs) such as Meetup, Plancast, etc., have become popular platforms for users to plan and organize social events with friends and acquaintances. These LBSNs and EBSNs provide rich content such as \textit{online} and \textit{offline} user interactions, location/event descriptions which can be leveraged for personalized group recommendations. In this paper, we propose novel Collaborative-Filtering based Bayesian models to capture the location semantics and the group dynamics such as user interactions, user-group membership, user influence etc., for personalized group recommendations. Empirical experiments on two large real-world datasets (Gowalla and Meetup) show that our models outperform the state-of-the-art group recommender systems. We discuss the group characteristics of our datasets and show that modeling of group dynamics learns better group preferences than aggregating individual user preferences. Moreover, our model provides human interpretable results which can be used to understand the group participation behavior and location/event popularity.

Simulating our LifeSteps by Example

During the last decades a number of effective methods for indexing, query processing, and knowledge discovery in moving object databases have been proposed. An interesting research direction that has recently emerged handles semantics of movement instead of raw spatio-temporal data. Semantic annotations, such as stop, move, at home, shopping, driving, etc., are either declared by the users (e.g. through social network apps) or automatically inferred by some annotation method and are typically presented as textual counterparts along with spatial and temporal information of raw trajectories. It is natural to argue that such spatio-temporal-textual sequences, called semantic trajectories, form a realistic representation model of the complex everyday life (hence, mobility) of individuals. Towards handling semantic trajectories of moving objects in Semantic Mobility Databases (SMD), the lack of real datasets leads to the need of designing realistic simulators. In the context of the above discussion, the goal of this work is to realistically simulate the mobility life of a large-scale population of moving objects in an urban environment. Two simulator variations are presented: the core Hermoupolis simulator is parametric-driven (i.e., user-defined parameters tune every movement aspect), whereas the expansion of the former, called Hermoupolisby-example, follows the generate-by-example paradigm and is self-tuned by looking inside a real small (sample) dataset. We stress test our proposal and demonstrate its novel characteristics with respect to related work.

Mining At Most Top-K% Spatiotemporal Co-occurrence Patterns in Data Sets with Extended Spatial Representations

Spatiotemporal co-occurrence patterns (STCOPs) in data sets with extended spatial representations are subsets of two or more different event types represented as polygons evolving in time, whose instances often occur together in both space and time. Finding STCOPs is an important problem with many application domains such as weather monitoring and solar physics. Nevertheless, it is difficult to find a suitable prevalence threshold without prior domain specific knowledge. In this paper we focus our work on the problem of mining at most top-K% of STCOPs for continuously evolving spatiotemporal events that have polygon-like representations, without using a user-specified prevalence threshold.

Efficient Processing of Relevant Nearest-Neighbor Queries

Novel Web technologies and resulting applications have lead to a participatory data ecosystem that when utilized properly will lead to more rewarding services. In this work, we investigate the case of Location-based Services and specifically of how to improve the typical location-based Point-Of-Interest (POI) request processed as a k-Nearest-Neighbor query. This work introduces Links-of-interest (LOI) between POIs as a means to increase the relevance and overall result quality of such queries. By analyzing user-contributed content in the form of travel blogs, we establish the overall popularity of a LOI, i.e., how frequently the respective POI pair is mentioned in the same context. Our contribution is a query processing method for so-called k-Relevant Nearest Neighbor (k-RNN) queries that considers spatial proximity in combination with LOI information to retrieve close-by and relevant (as judged by the crowd) POIs. Our method is based on intelligently combining indices for spatial data (a spatial grid) and for relevance data (a graph) during query processing. Using landmarks as a means to prune the search space in the Relevance Graph, we improve the proposed methods. Using in addition A -directed search, the query performance can be further improved. An experimental evaluation using real and synthetic data establishes that our approach efficiently solves the k-RNN problem.


Publication Years 2015-2016
Publication Count 16
Citation Count 4
Available for Download 16
Downloads (6 weeks) 199
Downloads (12 Months) 1894
Downloads (cumulative) 1198
Average downloads per article 75
Average citations per article 0
First Name Last Name Award
Timoleon Sellis ACM Senior Member (2008)
Cyrus Shahabi ACM Distinguished Member (2009)

First Name Last Name Paper Counts
Maria Damiani 2
Lars Kulik 2
Carola Wenk 1
Salles Magalhães 1
Timos Sellis 1
Pankaj Agarwal 1
Bettina Speckmann 1
Peter Scheuermann 1
Cyrus Shahabi 1
Alex Beutel 1
Yi Yu 1
Preeti Goel 1
Sara Migliorini 1
Martin Nöllenburg 1
Elisa Bertino 1
Sadao Obana 1
Karine Zeitouni 1
André Van Renssen 1
Claudio Silvestri 1
Marcus Andrade 1
Suhua Tang 1
Janne Kovanen 1
Mohammed Ali 1
Sarana Nutanong 1
Wouter Meulemans 1
Mark Mckennney 1
Andreas Gemsa 1
Jan Haunert 1
Georgios Skoumas 1
Thomas Mølhave 1
Chaulio Ferreira 1
Ralf Güting 1
Kotagiri Ramamohanarao 1
Egemen Tanin 1
Giuseppe Pelagatti 1
Hien To 1
Roger Frye 1
Gabriel Ghinita 1
Dai That 1
Brittany Fasy 1
Anastasios Kyrillidis 1
Mahmuda Ahmed 1
Roger Zimmermann 1
Tapani Sarjakoski 1
Iulian Popa 1
Kevin Buchin 1
Alberto Belussi 1
Wm Franklin 1
Dieter Pfoser 1
Fabio Valdes 1
Kyle Hickmann 1
Mauro Negri 1
Leyla Kazemi 1

Affiliation Paper Counts
National Technical University of Athens 1
University of Texas at San Antonio 1
Swinburne University of Technology 1
Carnegie Mellon University 1
Microsoft 1
City University London 1
Rensselaer Polytechnic Institute 1
University of Massachusetts Boston 1
Bangladesh University of Engineering and Technology 1
George Mason University 1
National University of Singapore 1
City University of Hong Kong 1
Ca' Foscari University of Venice 1
University of Texas at Austin 1
University of Osnabruck 1
Northwestern University 1
Duke University 1
Purdue University 1
University of Hagen 2
Research Organization of Information and Systems National Institute of Informatics 2
University of Verona 2
University of Southern California 2
Politecnico di Milano 2
University of Milan 2
University of Electro-Communications 2
Karlsruhe Institute of Technology 2
Eindhoven University of Technology 2
Southern Illinois University at Edwardsville 2
Federal University of Vicosa 3
Universite de Versailles Saint-Quentin-en-Yvelines 3
Tulane University 3
University of Melbourne 5

ACM Transactions on Spatial Algorithms and Systems - Invited Papers from ACM SIGSPATIAL

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