ACM Transactions on

Spatial Algorithms and Systems (TSAS)

Latest Articles

Efficient Processing of Relevant Nearest-Neighbor Queries

Novel Web technologies and resulting applications have led to a participatory data ecosystem that, when utilized properly, will lead to more rewarding... (more)

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

Spatiotemporal co-occurrence patterns (STCOPs) in datasets with extended spatial representations are... (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
Matching Labels and Markers in Historical Maps: an Algorithm with Interactive Postprocessing

We present an algorithmic system for determining the proper correspondence between place markers and their labels in historical maps. We assume that the locations of place markers (usually pictographs) and labels (pieces of text) have already been determined and want to match the labels to the markers. This time-consuming step in the digitization process of historical maps is nontrivial even for humans, but provides valuable metadata (for example when subsequently georeferencing the map). To speed up this process, we model the problem in terms of combinatorial optimization, solve that problem efficiently, and show how user interaction can be used to improve the quality of results. We also consider a version of the model where we are given label fragments and have to decide which fragments go together. We show that this problem is NP-hard and that a realistic, restricted version of of it can be solved in polynomial time. We have implemented the algorithm for the main problem and tested it on a manually-extracted ground truth. The algorithm correctly matches 99% of the labels and is robust against noisy input. It performs a sensitivity analysis and in this way computes a measure of confidence for each of the matches. We propose an interactive system where the user's effort is directed to checking the parts of the map where the algorithm is unsure; any corrections the user makes are propagated by the algorithm. We confirm statistically that this successfully locates the areas on the map where the algorithm needs help.

Online Spatial Event Forecasting in Microblogs

Event forecasting based on social media data streams is an significant problem. Existing approaches focus on forecasting temporal events (such as elections and sports) but as yet cannot forecast spatiotemporal events such as civil unrest and influenza outbreaks, which are much more challenging. To achieve spatiotemporal event forecasting, spatial features that evolve with time and their underlying correlations need to be considered and characterized. In this paper, we propose novel batch and online approaches for spatiotemporal event forecasting in social media such as Twitter. Our models characterize the underlying development of future events by simultaneously modeling the structural contexts and spatiotemporal burstiness based on different strategies. Both batch and online-based inference algorithms are developed to optimize the model parameters. Utilizing the trained model, the alignment likelihood of tweet sequences is calculated by dynamic programming. Extensive experimental evaluations on two different domains demonstrated the effectiveness of our proposed approach.

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.

On Local Expert Discovery via Geo-Located Crowds, Queries, and Candidates

Local experts are critical for many location-sensitive information needs, and yet there is a research gap in our understanding of the factors impacting who is recognized as a local expert and in methods for discovering local experts. Hence, in this paper, we explore a geo-spatial learning-to-rank framework for identifying local experts. Three of the key features of the proposed approach are: (i) a learning-based framework for integrating multiple user-based, content-based, list-based, and crowd-based factors impacting local expertise that leverages the fine-grained GPS coordinates of millions of social media users; (ii) a location-sensitive random walk that propagates crowd knowledge of a candidate's expertise; and (iii) a comprehensive controlled study over AMT-labeled local experts on eight topics and in four cities. We find significant improvements of local expert finding versus two state-of-the-art alternatives, as well as evidence for the generalizability of local expert ranking models to new topics and new locations.


Publication Years 2015-2016
Publication Count 18
Citation Count 5
Available for Download 18
Downloads (6 weeks) 319
Downloads (12 Months) 1980
Downloads (cumulative) 2198
Average downloads per article 122
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
Leyla Kazemi 1
Andreas Gemsa 1
Jan Haunert 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
Gabriel Ghinita 1
Dai That 1
Mahmuda Ahmed 1
Brittany Fasy 1
Anastasios Kyrillidis 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
Wouter Meulemans 1
Kyle Hickmann 1
Mauro Negri 1
Mark Mckennney 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 (TSAS)

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