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.

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 1
Available for Download 16
Downloads (6 weeks) 189
Downloads (12 Months) 1613
Downloads (cumulative) 1613
Average downloads per article 101
Average citations per article 0
First Name Last Name Award

First Name Last Name Paper Counts
Lars Kulik 2
Mauro Negri 1
Kyle Hickmann 1
Carola Wenk 1
Bettina Speckmann 1
Peter Scheuermann 1
Cyrus Shahabi 1
Yi Yu 1
Preeti Goel 1
Sara Migliorini 1
Martin Nöllenburg 1
Maria Damiani 1
Sadao Obana 1
Karine Zeitouni 1
André Van Renssen 1
Suhua Tang 1
Janne Kovanen 1
Mohammed Ali 1
Sarana Nutanong 1
Leyla Kazemi 1
Mark Mckennney 1
Andreas Gemsa 1
Jan Haunert 1
Ralf Güting 1
Kotagiri Ramamohanarao 1
Egemen Tanin 1
Giuseppe Pelagatti 1
Hien To 1
Roger Frye 1
Dai That 1
Mahmuda Ahmed 1
Brittany Fasy 1
Roger Zimmermann 1
Tapani Sarjakoski 1
Iulian Popa 1
Kevin Buchin 1
Fabio Valdes 1
Wouter Meulemans 1
Alberto Belussi 1

Affiliation Paper Counts
University of Texas at San Antonio 1
Northwestern University 1
University of Milan 1
Microsoft 1
City University London 1
Bangladesh University of Engineering and Technology 1
National University of Singapore 1
City University of Hong Kong 1
University of Osnabruck 1
Politecnico di Milano 2
University of Verona 2
University of Electro-Communications 2
University of Hagen 2
Research Organization of Information and Systems National Institute of Informatics 2
Southern Illinois University at Edwardsville 2
Eindhoven University of Technology 2
Karlsruhe Institute of Technology 2
University of Southern California 2
Universite de Versailles Saint-Quentin-en-Yvelines 3
Tulane University 3
University of Melbourne 5

ACM Transactions on Spatial Algorithms and Systems

Volume 2 Issue 2, June 2016  Issue-in-Progress
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