ACM Transactions on

Spatial Algorithms and Systems (TSAS)

Latest Articles

Detecting Deviations from Intended Routes Using Vehicular GPS Tracks

The Medial Axis of a Multi-Layered Environment and Its Application as a Navigation Mesh


Forthcoming Articles
Feature-based Map Matching for Low-Sampling-Rate GPS Trajectories

With the increasing availability of GPS-equipped mobile devices, location-based services have become an integral part of people's everyday life. Among one of the initial steps of positioning data management, map matching aims to reduce the uncertainty in a trajectory by matching the GPS points to the road network on a digital map. Most existing work has focused on estimating the likelihood of a candidate path based on the GPS observations, while neglecting to model the probability of a route choice from the perspective of drivers. Here we propose a novel feature-based map matching algorithm that estimates the cost of a candidate path based on both GPS observations and human factors. To take human factors into consideration is very important especially when dealling with low sampling rate data where most of the movement details are lost. Additionally, we simultaneously analyze a sebsequence of coherent GPS points by utilizing a new segment-based probabilistic map matching strategy, which is less susceptible to the noiseness of the positioning data. We have evaluated both the offline and the online versions of our proposed approach on a public large-scale GPS dataset, which consists of 100 trajectories distributed all over the world. The experimental results show that our method is robust to sparse data with large sampling intervals (e.g., 60 s - 300 s) and challenging track features (e.g., u-turns and loops). Our method obtains the state-of-the-art map matching accuracy with a competitive processing time compared with existing map matching approaches.

Weighted Aggregate Reverse Rank Queries

In marketing, helping manufacturers to find the matching preferences of potential customers for their products is an essential work especially in e-commerce analyzing with big data. The aggregate reverse rank query has been proposed to return top-$k$ customers who regard a given product bundling as highest aggregate rank than other customers, where the aggregate rank is defined as the sum of each product's rank. This query correctly reflects the request only when the customers consider the products in the product bundling equally. Unfortunately, rather than thinking products equally, in most cases, people buy a product bundling because they appreciate a special part of the bundling. Manufacturers, such as video games companies and cable television industries, are also willing to bundle some attractive products with less popular products for the purpose of maximum benefits or inventory liquidation. Inspired by the necessity of general aggregate reverse rank query for unequal thinking, we propose a weighted aggregate reverse rank query which treats the elements in product bundling with different weights to target customers from all aspects of thought. To solve this query efficiently, we first try a straightforward extension. Then we re-build the bound-and-filter framework for the weighted aggregate reverse rank query. We prove theoretically that the new approach finds the optimal bounds and develops the maximum efficient algorithm based on this bounds. The theoretical analysis and experimental results demonstrated the efficacy of the proposed methods.


Publication Years 2015-2018
Publication Count 39
Citation Count 24
Available for Download 39
Downloads (6 weeks) 277
Downloads (12 Months) 2403
Downloads (cumulative) 6109
Average downloads per article 157
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)
Ouri Wolfson ACM Fellows (2001)
Moustafa Amin Youssef ACM Distinguished Member (2015)
Roger Zimmermann ACM Distinguished Member (2017)

First Name Last Name Paper Counts
Dieter Pfoser 3
Rafal Angryk 2
Lars Kulik 2
Timos Sellis 2
Maria Damiani 2
Berkay Aydin 2
Petrus Martens 2
Dimitrios Skoutas 2
Thomas Van Dijk 1
Bo Xu 1
Heba Aly 1
Moustafa Youssef 1
Sophia Karagiorgou 1
Lidia Ortega 1
Hien To 1
Roger Frye 1
Gabriel Ghinita 1
Ralf Güting 1
Kotagiri Ramamohanarao 1
Egemen Tanin 1
Giuseppe Pelagatti 1
Alexander Wolff 1
Huiju Hung 1
Christodoulos Efstathiades 1
Dustin Kempton 1
Zhifeng Bao 1
Anas Basalamah 1
Kunta Chuang 1
Sanjay Chawla 1
Mahmuda Ahmed 1
Brittany Fasy 1
Anastasios Kyrillidis 1
Naren Ramakrishnan 1
Dai That 1
Sanjay Purushotham 1
Changtien Lu 1
Panagiotis Tampakis 1
George Papadakis 1
Bhaskar DasGupta 1
Xiaolin Hu 1
Radu Mariescu-Istodor 1
Ahmet Küçük 1
Francisco Feito 1
Wm Franklin 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
Pasi Fränti 1
Kyle Hickmann 1
Carola Wenk 1
Pankaj Agarwal 1
Salles Magalhães 1
Fabio Valdés 1
Wouter Meulemans 1
Mauro Negri 1
Benedikt Budig 1
Wei Niu 1
Alexandros Efentakis 1
Alexandros Belesiotis 1
Ouri Wolfson 1
Joël Estephan 1
Joachim Gudmundsson 1
Hitoshi Shimizu 1
Cyrus Shahabi 1
Alex Beutel 1
Bettina Speckmann 1
Peter Scheuermann 1
Feng Chen 1
Wangchien Lee 1
Karthik Pillai 1
Juan Banda 1
Stylianos Sideridis 1
Shane Culpepper 1
Weishinn Ku 1
Yuan Long 1
Tomoharu Iwata 1
Naonori Ueda 1
Martin Nöllenburg 1
Elisa Bertino 1
Yi Yu 1
Preeti Goel 1
Sara Migliorini 1
Chung Kuo 1
Nikos Pelekis 1
Shanyun Teng 1
Michael Horton 1
Claudio Silvestri 1
Marcus Andrade 1
Sadao Obana 1
Karine Zeitouni 1
André Van Renssen 1
Liang Zhao 1
Denian Yang 1
Daniel Ayala 1
Jie Lin 1
Farhana Choudhury 1
Daichi Amagata 1
Takahiro Hara 1
Futoshi Naya 1
M Robles-Ortega 1
Leyla Kazemi 1
Mark Mckennney 1
Andreas Gemsa 1
Jan Haunert 1
Thomas Mølhave 1
Chaulio Ferreira 1
Georgios Skoumas 1
Suhua Tang 1
Janne Kovanen 1
Mohammed Ali 1
Sarana Nutanong 1

Affiliation Paper Counts
Carnegie Mellon University 1
Auburn University 1
State University of New York at Albany 1
Rensselaer Polytechnic Institute 1
University of Athens 1
Umm Al Qura University 1
Northwestern University 1
University of Massachusetts Boston 1
Microsoft Corporation 1
Academia Sinica Taiwan 1
University of Texas at Austin 1
Bangladesh University of Engineering and Technology 1
University of Maryland 1
National University of Singapore 1
Purdue University 1
Montana State University - Bozeman 1
City University London 1
Osnabruck University 1
Duke University 1
University of Texas at San Antonio 1
Ca' Foscari University of Venice 1
Hamad bin Khalifa University 1
City University of Hong Kong 1
Stanford University 1
Virginia Tech 2
Pennsylvania State University 2
Eindhoven University of Technology 2
University of Milan 2
Athena Research and Innovation Center in Information, Communication and Knowledge Technologies 2
Karlsruhe Institute of Technology 2
University of Verona 2
University of Hagen 2
Politecnico di Milano 2
Osaka University 2
University of Electro-Communications 2
National Technical University of Athens 2
National Cheng Kung University 2
Research Organization of Information and Systems National Institute of Informatics 2
University of Eastern Finland 2
Southern Illinois University at Edwardsville 2
Swinburne University of Technology 2
Federal University of Vicosa 3
RMIT University 3
Tulane University 3
University of Wurzburg 3
Universite de Versailles Saint-Quentin-en-Yvelines 3
Universidad de Jaen 3
The University of Sydney 3
Texas A and M University System 3
University of Illinois at Chicago 3
University of Piraeus 4
George Mason University 4
Nippon Telegraph and Telephone Corporation 4
University of Southern California 4
University of Melbourne 5
Georgia State University 10

ACM Transactions on Spatial Algorithms and Systems (TSAS)

Volume 4 Issue 1, May 2018  Issue-in-Progress
Volume 3 Issue 4, May 2018

Volume 3 Issue 3, November 2017
Volume 3 Issue 2, August 2017 SIGSPATIAL Paper and Regular Papers
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