Finding Traffic-Aware Fastest Paths in Spatial Networks

Shuo Shang, Hua Lu, Torben Bach Pedersen, Xike Xie

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningpeer review

Abstract

Route planning and recommendation have received significant attention in recent years. In this light, we propose and investigate the novel problem of finding traffic-aware fastest paths (TAFP query) in spatial networks by considering the related traffic conditions. Given a sequence of user specified intended places O q and a departure time t, TAFP finds the fastest path connecting O q in order to guarantee that moving objects (e.g., travelers and bags) can arrive at the destination in time. This type of query is mainly motivated by indoor space applications, but is also applicable in outdoor space, and we believe that it may bring important benefits to users in many popular applications, such as tracking VIP bags in airports and recommending convenient routes to travelers. TAFP is challenged by two difficulties: (i) how to model the traffic awareness practically, and (ii) how to evaluate TAFP efficiently under different query settings. To overcome these challenges, we construct a traffic-aware spatial network G ta (V,E) by analysing uncertain trajectory data of moving objects. Based on G ta (V,E), two efficient algorithms are developed based on best-first and heuristic search strategies to evaluate TAFP query. The performance of TAFP has been verified by extensive experiments on real and synthetic spatial datasets
OriginalsprogEngelsk
TitelAdvances in Spatial and Temporal Databases - 13th International Symposium, SSTD 2013, Munich, Germany, August 21-23, 2013. Proceedings
RedaktørerMario A. Nascimento, Timos K. Sellis, Reynold Cheng, Jörg Sander, Yu Zheng, Hans-Peter Kriegel, Matthias Renz, Christian Sengstock
Antal sider18
Vol/bind8098
ForlagSpringer
Publikationsdato2013
Sider128-145
ISBN (Trykt)978-3-642-40234-0
ISBN (Elektronisk)978-3-642-40235-7
DOI
StatusUdgivet - 2013
Udgivet eksterntJa
Begivenhed13th International Symposium on Spatial and Temporal Databases - München, Tyskland
Varighed: 21 aug. 201323 aug. 2013
Konferencens nummer: 13

Konference

Konference13th International Symposium on Spatial and Temporal Databases
Nummer13
Land/OmrådeTyskland
ByMünchen
Periode21/08/201323/08/2013
NavnLecture Notes in Computer Science
Nummer8098

Citer dette