ACM Transactions on

Spatial Algorithms and Systems (TSAS)

Latest Articles

Snap Rounding with Restore

This article presents a new algorithm called Snap Rounding with Restore (SRR), which aims to make geometric datasets robust and to increase the quality of geometric approximation and the preservation of topological structure. It is based on the well-known Snap Rounding algorithm but improves it by eliminating from the snap rounded arrangement the... (more)

Area-Preserving Simplification and Schematization of Polygonal Subdivisions

In this article, we study automated simplification and schematization of territorial outlines. We present a quadratic-time simplification algorithm... (more)

Spatial Consensus Queries in a Collaborative Environment

We introduce a new type of query for a location-based social network platform. Consider a scenario in which a group of users is trying to find a... (more)

Privacy-Aware Dynamic Ride Sharing

Dynamic ride sharing is a service that enables shared vehicle rides in real time and on short notice. It can be an effective solution to counter the problem of increasing traffic jams at peak hours in cities. The growing use and popularity of smart phones and GPS-enabled devices provides us with tools required to efficiently implement ride sharing... (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
Location Estimation Using Crowdsourced Spatial Relations

The ``crowd'' has become a very important geospatial data provider. Subsumed under the term Volunteered Geographic Information (VGI), non-expert users have been providing a wealth of quantitative geospatial data online. With spatial reasoning being a basic form of human cognition, narratives expressing geospatial experiences, e.g., travel blogs, would provide an even bigger source of geospatial data. Textual narratives typically contain qualitative data in the form of objects and spatial relationships. The scope of this work is (i) to extract these relationships from user-generated texts, (ii) to quantify them and (iii) to reason about object locations based only on this qualitative data. We use information extraction methods to identify toponyms and spatial relationships and we formulate a quantitative approach based on distance and orientation features to represent the latter. Positional probability distributions for spatial relationships are determined by means of a greedy Expectation Maximization-based (EM) algorithm. These estimates are then used to ``triangulate'' the positions of unknown object locations. Experiments using a text corpus harvested from travel blog sites establish the considerable location estimation accuracy of the proposed approach on synthetic and real world scenarios.

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.

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

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.

An efficient external memory algorithm for terrain viewshed computation

This paper presents TiledVS, a fast external algorithm and implementation for computing viewsheds. TiledVS is intended for terrains that are too large for internal memory, even over 100000x100000 points. It subdivides the terrain into tiles, that are stored compressed on disk and then paged into memory with a custom cache data structure and LRU algorithm. If there is sufficient available memory to store a whole row of tiles, which is easy, then this specialized data management is faster than relying on the operating system's virtual memory management. Applications of viewshed computation include siting radio transmitters, surveillance, and visual environmental impact measurement. TiledVS runs a rotating line of sight from the observer to points on the region boundary. For each boundary point, it computes the visibility of all the terrain points close to the line of sight. The running time is linear in the number of points. No terrain tile is read more than twice. TiledVS is very fast, for instance, processing a 104000x104000 terrain on a modest computer with only 512MB of RAM took only 1.5 hours. On large datasets, TiledVS was several times faster than competing algorithms such as are in GRASS. The source code of TiledVS is freely available for nonprofit researchers to study, use, and extend. An earlier version of this algorithm was published in a 4-page ACM SIGSPATIAL 2012 conference paper. This more detailed version adds the fast lossless compression stage that reduces the time by 30% to 40%, and many more experiments and comparisons.


Publication Years 2015-2016
Publication Count 12
Citation Count 1
Available for Download 12
Downloads (6 weeks) 222
Downloads (12 Months) 1465
Downloads (cumulative) 1142
Average downloads per article 95
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
André Van Renssen 1
Karine Zeitouni 1
Suhua Tang 1
Janne Kovanen 1
Sarana Nutanong 1
Mohammed Ali 1
Andreas Gemsa 1
Jan Haunert 1
Leyla Kazemi 1
Mark Mckennney 1
Ralf Güting 1
Kotagiri Ramamohanarao 1
Egemen Tanin 1
Giuseppe Pelagatti 1
Roger Frye 1
Hien To 1
Dai That 1
Brittany Fasy 1
Mahmuda Ahmed 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 1, April 2016

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